I know that if we want the last 10 decimal digits of $1234^{1234^{1234}}$ we should compute $1234^{1234^{1234} \bmod\ \phi(10^{10})} \bmod 10^{10}$ to keep the exponent small. And that technically, $1234^{1234^{1234}\ \bmod\ 10^{10}} \bmod 10^{10}$ is incorrect. Yet they are equal. Why?
Why does $1234^{1234^{1234}\ \bmod\ 10^{10}}$ = $1234^{1234^{1234}\ \bmod \ \phi(10^{10})}$
-
0I mean why are they equal for these particular constants even though the approach, in general, is flawed. Is this an artifact of base 10? Does 1234 have a particular property? Or does this always work for any base and any constant? – 2012-10-26
2 Answers
$\phi(10^{10})=4\cdot 10^9$ divides $2\cdot 10^{10}$, so we'd still get a right answer if we considered the exponent mod $2\cdot 10^{10}$. Now we note that every equivalence class mod $10^{10}$ corresponds to 2 equivalence classes mod $2\cdot 10^{10}$ so that should give you about 50-50 odds of getting it the right result (if there's not more going on).
In general of course $\phi(n)$ doesn't nearly divide $n$, as it does here, so it's pretty specific to this problem (although it does generalize to other powers of $10$).
Edit: There is in fact slightly more going on since while $\phi(n)$ is the order of the multiplicative group modulo $n$, if the group isn't cyclic, it's not necessarily true that the least common multiple of all the orders in the group is $\phi(n)$. Denoting the multiplicative group modulo $n$ by $R_n$, the Chinese Remainder Theorem tells us that $R_{10^{10}}=R_{2^{10}}\times R_{5^{10}}$ and there's a nice structure theorem for these groups that tells us that $R_{2^{10}}=C_2\times C_{2^8}$, where $C_n$ is the cyclic group with $n$ elements. In particular the least common multiple of the orders of elements of $R_{2^{10}}$ is $2^8$ instead of $2^9$ so it'll be generally correct to take the exponent mod $\frac{\phi(10^{10})}{2}$ which does divide $10^{10}$.
-
0The method requires $a$ and $10^{10}$ to be coprime, not just for $a$ to not be$a$multiple of 10. It is not true that $2^{\phi(10^{10})+1}\equiv 2$mod $10^{10}$; it's just really likely you'll get the right answer anyway since most equivalence classes mod $10^{10}$ are greater than $10$. – 2012-10-27
Earlier incorrect post: Note that $\phi(10^{10}) = 2 \cdot 10^9$ divides $10^{10}$.
Correction: My mistake, $\phi(10^{10}) = 2^{11} \cdot 5^9$, as several commenters noticed.
Let $A: = {1234^{1234}}, \; a:= A \mod 10^{10}, \; b: = A \mod \phi(10^{10})$. To show that $1234^a \equiv 1234^b \mod 10^{10}$, it is enough to show that $1234^a \equiv 1234^b \mod 2^{10}$ and $1234^a \equiv 1234^b \mod 5^{10}$ and use the Chinese Remainder Theorem.
Now clearly $1234^a \equiv 1234^b \equiv 0 \mod 2^{10}$, since $a, \, b > 10$.
To show $1234^a \equiv 1234^b \mod 5^{10}$, we use Euler's Theorem and thus must show that $a \equiv b \mod \phi(5^{10})$. Now $n = \phi(5^{10}) = 4 \cdot 5^9$, which divides both $M = 10^{10}$ and $N = \phi(10^{10})$. Consequently $ a \mod n \equiv (A \mod M) \mod n \equiv (A \mod N ) \mod n = b \mod n \, .\ $
Therefore the two computations give the same result.
-
0Th$a$nks, it has now $b$een corrected. – 2012-10-26