View Single Post
Old 2013-02-13, 17:17   #10
Nick
 
Nick's Avatar
 
Dec 2012
The Netherlands

32×132 Posts
Default

Wow, thanks for all the responses to the first puzzle, both answers and links.

Mathematically, the pattern arises because we use decimal notation and there are 2 distinct primes dividing 10 (it wouldn't work in hexadecimal, for example).
For any positive integer n the Chinese Remainder Theorem tells us that \mathbb{Z}/10^n\mathbb{Z} is isomorphic to \mathbb{Z}/5^n\mathbb{Z}\times\mathbb{Z}/2^n\mathbb{Z}.

As fivemack pointed out, it follows that in the integers modulo 10ⁿ there are 4 idempotent elements (numbers equal to their own square), not just 0 and 1 (corresponding with the pairs (0,0) and (1,1)) but also the numbers corresponding with (1,0) and (0,1) via the isomorphism above.
Thus, for example, 625 is the unique integer modulo 1000 which is congruent to 0 mod 125 and 1 mod 8, while 376 is the unique integer modulo 1000 which is congruent to 1 mod 125 and 0 mod 8. And their sum 625+376 is congruent to 1 mod 1000 because (again as fivemack noted) if e is idempotent then so is 1-e.

Last fiddled with by Nick on 2013-02-13 at 17:19
Nick is offline   Reply With Quote