Problem: Calculate $10^{10^{10}} \pmod 7$
According to Fermat's little theorem: $a^{p-1}\equiv1 \pmod p$, so $10^6\equiv1 \pmod 7$ and $10^n\equiv4 \pmod 6$, $n$ being any integer, why can we write $10^{10^{10}}\equiv10^4 \pmod 7$?
Similarly, if it's $10^n\equiv1 \pmod 3$, n being any integer, then wouldn't the equation become $10^{10^{10}}\equiv10^1\equiv3\pmod 7$? I'm confused on the translation phase.
Thanks
$\endgroup$ 15 Answers
$\begingroup$Let's first examine the proof in detail, before turning to the key idea that makes it work (which you seem to be striving towards in your nice observation).
Note $\rm\ mod\,\ 7\!:\ 10^6\equiv 1\ \Rightarrow\ 10^{\,\large n}\!\color{#c00}\equiv 10^{\Large{\, (n\ mod\ 6)}}\ $ by little Fermat (see comments for proof).
Here $\rm\ mod\,\ 6\!:\ 10\equiv 4,\,\ 4^2\equiv 4,\,$ so $\,\color{#0a0}{10^{10}\equiv 4^{10}\equiv 4}$
Thus $\rm\ mod\ 7\!:\ 10^{\Large{10^{10}}\!\!}\color{#c00}\equiv 10^{\,\large{\color{#0a0}{(10^{10}\, mod\ 6)}}}\equiv 10^{\,\color{#0a0}4}\equiv 3^4 \equiv 2^2\equiv 4$
Your observation is very close to the key idea: the reason that the proof works is the following. If $\rm\,k\equiv 1\pmod 3\,$ and $\rm\,k\equiv 0\pmod 2\,$ then $\rm\,k^n \equiv k\,$ holds both mod $3$ and mod $2$ so also mod $6$, hence we deduce $10^{\,k^n}\!\equiv 10^k\pmod 7$. In essence we have lifted up the "easy power property" $x^2 = x\,\Rightarrow\, x^n = x\,$ from the universal easily powerable elements $\,1,0\,$ to a pair of them $\rm\,4 \equiv (1,0)\ (mod\ 3,2)\ $ also, a solution, since $\rm (1,0)^2 \equiv (1,0).$
Generally solutions of $\,x^2 = x\,$ are called idempotents. They play fundamental roles in factorization of rings and their elements - something that will become much clear if one goes on to study the Chinese Remainder Theorem in an abstract algebra course.
$\endgroup$ 3 $\begingroup$I believe your argument is correct. To compute $10^{10^{10}} \pmod{7}$ you can first compute $10^{10} \pmod{6}$. In turn, you can do this modulo $2$ and $3$, so you get that $10^{10} \equiv 4 \pmod{6}$, and $10^{10^{10}} \equiv 3^{4} \equiv 2 \cdot 2 \equiv 4 \pmod{7}$.
$\endgroup$ 2 $\begingroup$In simplest methods,
$$10^{10^{10}} \equiv 10^{\big(1+3k\big)} \equiv 10 \cdot (-1)^k \equiv 4 \pmod7$$
For some odd $k$, which follows from the fact that $10^{10} \neq 1 \pmod{6}$
$\endgroup$ $\begingroup$Let me see if I can make it clear
Starting with $10^6 \equiv 1 \mod 7$, we have $$ \begin{align} 10^{12} &= \left(10^6\right)^2 \equiv 1^2 = 1 \mod 7\\ 10^{18} &= \left(10^6\right)^3 \equiv 1^3 = 1 \mod 7\\ 10^{24} &= \left(10^6\right)^4 \equiv 1^4 = 1 \mod 7\\ \cdots& \end{align} $$
This tells us how to find $10^n \mod 7$. For example, if I want $10^{73} \mod 7$ $$ 10^{73} = 10^{72 + 1} = 10^{72}\, 10 = \left(10^6\right)^{12} ~10 = 10 \mod 7 = 3 $$ In general when calculating $a^n \mod p$ where $p$ is a prime, we cast off multiples of $p-1$ from n i.e. $$ a^n \mod p \equiv a^m \mod p ~~\hbox{where $n \equiv m \mod (p-1)$ }$$
Note: If $p$ is not a prime, then replace $p-1$ by $\phi(p)$
$\endgroup$ $\begingroup$As $\displaystyle10^3=1000\equiv-1\pmod7$
and for integer $\displaystyle n\ge1,10^n=3\cdot\underbrace{33\cdots33}_{n \text{ digits}}+1=3r+1$ where $r$ is an odd positive integer
$\displaystyle\implies 10^{(10^n)}=10^{3r+1}=10\cdot(10^3)^r\equiv10\cdot(-1)^r\pmod7\equiv-10\equiv4$
$\endgroup$
