# Why does $1234^{1234^{1234}\ \bmod\ 10^{10}}$ = $1234^{1234^{1234}\ \bmod \ \phi(10^{10})}$

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?

-
What do you mean by "why"? – M.B. Oct 26 '12 at 19:23
I 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? – Fixee Oct 26 '12 at 19:32

$\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}$.

-
I just tried it for 1000 values other than 1234, and it always works. Assuming your argument above is correct, there is only a 1 in $2^{1000}$ chance that was just luck, so there is something missing here still. – Fixee Oct 26 '12 at 19:53
You're right. I've worked it out fully now. – anonymous Oct 26 '12 at 21:17
Does it affect your answer at all that 1234 $\not\in R_{10^{10}}$? – Fixee Oct 27 '12 at 3:49
Also, the LCM of all group orders (for periodic groups) is called the "exponent" of the group. Although this seems to not be very well-known (for example, Wolfram Alpha appears to not know the term). – Fixee Oct 27 '12 at 3:52
Well, uh, the basic method is already faulty (in that $10^{\phi(10^{10})+1}\equiv 0$ mod $10^{10}$ and not $10$ mod $10^{10}$. My answer isn't particularly more wrong. – anonymous Oct 27 '12 at 11:42

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.

-
No, $\phi(10^{10}) = 4\cdot 10^9$. – M.B. Oct 26 '12 at 19:13
$\phi(10^{10}) = \phi(2^{10})\phi(5^{10}) = 2^9 \cdot 4\cdot 5^9$. – Fixee Oct 26 '12 at 19:16
Thanks, it has now been corrected. – Hans Engler Oct 26 '12 at 21:35