$10^7 \pmod {77}$
I tried repeated squaring, which worked but took many computations. I also tried Fermat's little theorem, but since $7 < 77$ I didn't know how to use it.
Any simpler way to do this?
Asked
Active
Viewed 583 times
2 Answers
0
For such a small exponent, just computing it directly works:
\begin{align} 10^2 = 100 &\equiv 23 \pmod{77} \\ 10^3 \equiv 230 &\equiv -1 \pmod{77} \\ 10^6 \equiv (-1)^2 &\equiv 1 \pmod{77} \\ 10^7 \equiv 10 \cdot 1 &\equiv 10 \pmod{77} \end{align}
Another way is to notice that $1000 = 1001 - 1 = 7\cdot 11 \cdot 13 - 1 \equiv -1 \pmod{7}$
0
Not much effort saved, but work separately mod $11$ (easy, since $10\equiv -1\pmod{11}$) and mod $7$ (easy since by Fermat $10^7\equiv 10\pmod 7$). Then stitch the answers together using the Chinese Remainder Theorem. In this case that can be done by inspection: the answer is $10$.
André Nicolas
- 507,029
-
Since $10\equiv -1\pmod{11}$, $10^7=(-1)^7=-1\pmod{11}$. And $10^7\equiv 10\pmod 7$.... I'm looking at https://www.math.okstate.edu/~wrightd/crypt/lecnotes/node21.html. How do you apply the Chinese Remainder Theorem? – Frank Epps Sep 26 '13 at 06:56
-
We don't really have to. We want something congruent to $10$ modulo $11$ and modulo $7$. Answer is $10$ (modulo $77$). If it was not as obvious as in this case, a short search would do it. For example if we had result $\equiv 4\pmod{7}$ and $\equiv 10\pmod{11}$, we would look at $10,21,32,43,\dots$ until we got something that had remainder $4$ on division by $7$. In the pretend case that's $32$. That works nicely for smallish numbers. For big ones we use the full CRT machinery. – André Nicolas Sep 26 '13 at 07:04