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,
ap≡a(modp)
If a is not divisible by p, Fermat's little theorem is equivalent
ap−1≡1(modp)
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.
ap−1≡1(modp)13599−1≡1(mod599)13598≡1(mod599)
131031(mod599)≡13598+433(mod599)≡13598⋅13433(mod599)|13598(mod599)=1≡1⋅13433(mod599)≡13433(mod599)≡138⋅54+1(mod599)≡(138)54⋅13(mod599)|138(mod599)=541≡54154⋅13(mod599)≡5413⋅18⋅13(mod599)≡(5413)18⋅13(mod599)|5413(mod599)=162≡16218⋅13(mod599)≡1623⋅6⋅13(mod599)≡(1623)6⋅13(mod599)|1623(mod599)=425≡4256⋅13(mod599)≡4253⋅2⋅13(mod599)≡(4253)2⋅13(mod599)|4253(mod599)=181≡1812⋅13(mod599)≡425893(mod599)≡4(mod599)