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