What is the remainder of: 13^1031 mod 599 =? Thanks for help.
Fermat's little theorem states that if p is a prime number, then for any integer a,
\({\displaystyle a^{p}\equiv a{\pmod {p}}}\)
If a is not divisible by p, Fermat's little theorem is equivalent
\( {\displaystyle a^{p-1}\equiv 1{\pmod {p}}}\)
see: https://en.wikipedia.org/wiki/Fermat%27s_little_theorem
Let p = 599 (prime number)
Let a = 13 (prime number)
gcd(13,599) = 1 ! so 13 and 599 are relatively prime, we can use Fermat's little theorem.
\(\begin{array}{|rcll|} \hline a^{p-1} &\equiv& 1{\pmod {p}} \\ 13^{599-1} &\equiv& 1{\pmod {599}} \\ 13^{598} &\equiv& 1{\pmod {599}} \\ \hline \end{array} \)
\(\begin{array}{|rcll|} \hline && 13^{1031} \pmod{599} \\ &\equiv & 13^{598+433} \pmod{599} \\ &\equiv & 13^{598}\cdot 13^{433} \pmod{599} \quad & | \quad 13^{598} \pmod{599} = 1 \\ &\equiv & 1\cdot 13^{433} \pmod{599} \\ &\equiv & 13^{433} \pmod{599} \\ &\equiv & 13^{8\cdot 54 + 1} \pmod{599} \\ &\equiv & (13^{8})^{54}\cdot 13 \pmod{599} \quad & | \quad 13^8 \pmod{599} = 541 \\ &\equiv & 541^{54}\cdot 13 \pmod{599} \\ &\equiv & 541^{3\cdot 18 }\cdot 13 \pmod{599} \\ &\equiv & (541^{3})^{18}\cdot 13 \pmod{599} \quad & | \quad 541^3 \pmod{599} = 162 \\ &\equiv & 162^{18}\cdot 13 \pmod{599} \\ &\equiv & 162^{3\cdot 6}\cdot 13 \pmod{599} \\ &\equiv & (162^{3})^{6}\cdot 13 \pmod{599} \quad & | \quad 162^3 \pmod{599} = 425 \\ &\equiv & 425^{6}\cdot 13 \pmod{599} \\ &\equiv & 425^{3\cdot 2}\cdot 13 \pmod{599}\\ &\equiv & (425^{3})^{2}\cdot 13 \pmod{599} \quad & | \quad 425^3 \pmod{599} = 181 \\ &\equiv & 181^{2}\cdot 13 \pmod{599} \\ &\equiv & 425893 \pmod{599} \\ &\equiv & 4 \pmod{599} \\ \hline \end{array}\)