Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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

2 Answers 2

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

share|improve this answer
    
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.

share|improve this answer
2  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.