2
$\begingroup$

By a modified version of the Fermat's little theorem we obtain that $a^{\phi(n)} \equiv 1$ mod $n$ whenever $(a,n)=1$. But my professor accidentally gave this question to calculate $2^{9999 }$ mod $100$. So everyone in the class calculated it using the theorem since they forgot to check that $(a,n)=1$. But to my surprise everyone got $88$ as the answer which is actually the correct answer.

So I first saw what happens in the case of mod $10$. Here $2^4 \equiv 6$ mod $10$. But magically enough this number multiplies with powers of $2$ as if it were identity i.e.

$$2\cdot6 \equiv 2 \pmod {10}$$

$$4\cdot6 \equiv 4 \pmod {10}$$

$$6\cdot6 \equiv 6 \pmod {10}$$

$$8\cdot6 \equiv 8 \pmod {10}$$

After seeing this I checked what happens in the case of $100$. Similar thing happens even here instead $2^{40} \equiv 76\pmod{100}$. Now $76 $ acts like $6$ just that $76*2 \neq 2$ but otherwise $76*4=4$ and $76*8=8$ and so on. Can anyone explain as to why it is happening here and does it happen in other cases as well.

$\endgroup$
  • $\begingroup$ Hint: $2^{9999}\equiv 0\pmod 4$. So you only need to solve $2^{9999}\pmod {25}$, and then solve the Chinese Remainder Theorem question. $\endgroup$ – Thomas Andrews Jan 20 '15 at 4:38
  • $\begingroup$ @ThomasAndrews $2^{20} \equiv 1 \pmod{25}$ So using that I solved it but I was amazed at how $76$ acted like $1$ and I want to know whether it happens with other numbers as well $\endgroup$ – happymath Jan 20 '15 at 4:41
  • 1
    $\begingroup$ To comment on the pattern you noticed: $6 = 5+1$, and $10 = 2\cdot 5$. So for any even number $n$: $6\cdot n\equiv 5\cdot n + 1\cdot n\equiv 0 + n\equiv n\pmod{10}$. $76$ behaves in a similar way because $76 = 75+1 = 3\cdot 25 + 1$ and $100 = 4\cdot 25$. If you multiply $76$ by a number divisible by $4$, it'll cancel off the $3\cdot 25$, but multiplying by even numbers that aren't divisible by $4$ doesn't cancel it completely (try $6$). $\endgroup$ – Stahl Jan 20 '15 at 4:42
  • $\begingroup$ @Stahl thanks so when all can I do this kind of a trick? $\endgroup$ – happymath Jan 20 '15 at 4:43
  • $\begingroup$ I'll add a comment about that to the answer I just wrote up. $\endgroup$ – Stahl Jan 20 '15 at 4:44
1
$\begingroup$

What's going on here is a direct result of the prime factorizations of $10 = 2\cdot 5$ and $100 = 2^2\cdot 5^2$. Try writing it like this: \begin{align*} 2\cdot 6\equiv 2\cdot(5+1)&\equiv 2\cdot 5 + 2\cdot 1\equiv 0 + 2\pmod{10}\\ 4\cdot 6&\equiv4\cdot 5 + 4\cdot 1\equiv 0 + 4\pmod{10} \end{align*} and so on. Since $6 = 5+1$, multiplying by an even number will "cancel out" the $5$, and you'll just be left with the $1$, acting like an identity. Same thing is going on with $76 = 75 + 1 = 3\cdot 25 + 1$. To cancel out the $3\cdot 25$, you need an even number that's divisible by $4$ ($4\cdot 25 = 100$). If you test $76\cdot 6\pmod{100}$, you should find that the result is nonzero.

This sort of thing will happen whenever you're calculating mod $n = \prod_{i = 1}^m p_i^{e_i}$ (here $\prod_{i = 1}^m p_i^{e_i}$ is the prime factorization of $n$) and you look at multiplication by a number $k$ of the form $1 + (\textrm{anything})(\textrm{product of some of the }p_i\textrm{'s})$. Whenever you multiply $k$ by any number whose factorization includes the $p_i$'s not appearing in the "product of some of the $p_i$'s" (counted with multiplicity), you'll cancel off the second term of $k$ and be left essentially multiplying by $1$. As an easy example, look mod $6$. Multiplication by $3$ acts like the identity for $3$ and $0$ because $3 = 1 + 2$ and $6 = 2\cdot 3$.

$\endgroup$
1
$\begingroup$

If $x\equiv 1\pmod{5^k}$, then $x\cdot (2^ka)\equiv 2^ka\pmod{10^k}$ for any integer $a$.

That's because $2^kax-2^ka=2^ka(x-1)$ is divisible by $2^k$ and by $5^k$, hence divisible by $10^k$.

More generally, if $x\equiv 1\pmod {m}$ then $x(nk)\equiv nk\pmod{mn}$ for any $n,k$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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