|
I am reading a document which states: By Fermat's Little Theorem, $a^{p-1}\bmod p = 1$. Therefore, $a^{b^c}\bmod p = a^{b^c\bmod (p - 1)} \bmod p$ For the life of me, I cannot figure out the logic of that conclusion. Would someone mind explaining it? I will be forever in your debt. Thank you! |
||||
|
|
|
Use the division algorithm to write $b^c=q(p-1)+r$ for some integers $q$ and $r$ such that $0\le r<p-1$; clearly $r=b^c\bmod{(p-1)}$. Now $$a^{b^c}=a^{q(p-1)+r}=\left(a^{p-1}\right)^q\cdot a^r\;,$$ and $a^{p-1}\equiv 1\pmod p$, so $$a^{b^c}\equiv a^r\pmod p\;.$$ |
|||
|
|
|
The key point is that if $\rm\ a^n = 1\ $ then exponents on $\rm\ a\ $ may be reduced mod $\rm\,n,\,$ viz. Hint $\rm\quad a^n = 1\ \,\Rightarrow\,\ a^i = a^j\ \ { if} \ \ i\equiv j\,\ (mod\ n)\:$ Proof $\rm\ \ i = j\!+\!nk\:$ $\Rightarrow$ $\rm\:a^i = a^{j+nk} = a^j (a^n)^k = a^j 1^k = a^j\ \ $ QED Yours is the special case $\rm\:0\ne a\in \Bbb Z/p,\:$ so $\rm\:a^{p-1}\! = 1,\:$ so exponents may be reduced mod $\rm\:p\!-\!1.$ Remark $\ $ You should check that proof works ok if $\rm\,k < 0\:$ (hint: $\rm\: a^n = 1\:\Rightarrow\: a\,$ is invertible, so negative powers of $\rm\,a\,$ are well-defined). The innate structure will become clearer if you study university algebra, where you will learn about cyclic groups, orders of elements, and order ideals, and modules. |
||||
|
|
