What is the remainder of: 13^1031 mod 599 =?
\(\begin{array}{|rcll|} \hline && 13^{1031} \pmod{599} \\ &\equiv & 13^{2\cdot 515+1} \pmod{599} \\ &\equiv & (13^{2})^{515}\cdot 13 \pmod{599} \quad & | \quad 13^2 \pmod{599} = 169 \\ &\equiv & 169^{515}\cdot 13 \pmod{599} \\ &\equiv & 169^{2\cdot 257+1}\cdot 13 \pmod{599} \\ &\equiv & (169^{2})^{257}\cdot 169 \cdot 13 \pmod{599} \quad & | \quad 169^2 \pmod{599} = 408 \\ &\equiv & 408^{257}\cdot 169 \cdot 13 \pmod{599} \\ &\equiv & 408^{2\cdot 128+1}\cdot 169 \cdot 13 \pmod{599} \\ &\equiv & (408^{2})^{128}\cdot 408 \cdot 169 \cdot 13 \pmod{599} \quad & | \quad 408^2 \pmod{599} = 541 \\ &\equiv & 541^{128}\cdot 408 \cdot 169 \cdot 13 \pmod{599} \\ &\equiv & (541^{2})^{64}\cdot 408 \cdot 169 \cdot 13 \pmod{599} \quad & | \quad 541^2 \pmod{599} = 369 \\ &\equiv & 369^{64}\cdot 408 \cdot 169 \cdot 13 \pmod{599} \\ &\equiv & (369^{2})^{32}\cdot 408 \cdot 169 \cdot 13 \pmod{599} \quad & | \quad 369^2 \pmod{599} = 188 \\ &\equiv & 188^{32}\cdot 408 \cdot 169 \cdot 13 \pmod{599} \\ &\equiv & (188^{2})^{16}\cdot 408 \cdot 169 \cdot 13 \pmod{599} \quad & | \quad 188^2 \pmod{599} = 3 \\ &\equiv & 3^{16}\cdot 408 \cdot 169 \cdot 13 \pmod{599} \quad & | \quad 3^{16} = 43046721 \pmod{599} = 185 \\ &\equiv & 185\cdot 408 \cdot 169 \cdot 13 \pmod{599} \\ &\equiv & 165829560 \pmod{599} \\ &\equiv & 4 \pmod{599} \\ &\equiv &\mathbf{ 4 }\\ \hline \end{array}\)
What is the remainder of: 13^1031 mod 599 =?
\(\begin{array}{|rcll|} \hline && 13^{1031} \pmod{599} \\ &\equiv & 13^{2\cdot 515+1} \pmod{599} \\ &\equiv & (13^{2})^{515}\cdot 13 \pmod{599} \quad & | \quad 13^2 \pmod{599} = 169 \\ &\equiv & 169^{515}\cdot 13 \pmod{599} \\ &\equiv & 169^{2\cdot 257+1}\cdot 13 \pmod{599} \\ &\equiv & (169^{2})^{257}\cdot 169 \cdot 13 \pmod{599} \quad & | \quad 169^2 \pmod{599} = 408 \\ &\equiv & 408^{257}\cdot 169 \cdot 13 \pmod{599} \\ &\equiv & 408^{2\cdot 128+1}\cdot 169 \cdot 13 \pmod{599} \\ &\equiv & (408^{2})^{128}\cdot 408 \cdot 169 \cdot 13 \pmod{599} \quad & | \quad 408^2 \pmod{599} = 541 \\ &\equiv & 541^{128}\cdot 408 \cdot 169 \cdot 13 \pmod{599} \\ &\equiv & (541^{2})^{64}\cdot 408 \cdot 169 \cdot 13 \pmod{599} \quad & | \quad 541^2 \pmod{599} = 369 \\ &\equiv & 369^{64}\cdot 408 \cdot 169 \cdot 13 \pmod{599} \\ &\equiv & (369^{2})^{32}\cdot 408 \cdot 169 \cdot 13 \pmod{599} \quad & | \quad 369^2 \pmod{599} = 188 \\ &\equiv & 188^{32}\cdot 408 \cdot 169 \cdot 13 \pmod{599} \\ &\equiv & (188^{2})^{16}\cdot 408 \cdot 169 \cdot 13 \pmod{599} \quad & | \quad 188^2 \pmod{599} = 3 \\ &\equiv & 3^{16}\cdot 408 \cdot 169 \cdot 13 \pmod{599} \quad & | \quad 3^{16} = 43046721 \pmod{599} = 185 \\ &\equiv & 185\cdot 408 \cdot 169 \cdot 13 \pmod{599} \\ &\equiv & 165829560 \pmod{599} \\ &\equiv & 4 \pmod{599} \\ &\equiv &\mathbf{ 4 }\\ \hline \end{array}\)
Mmm
I do not know the best way to do this but I will give it a go
13^1031 mod 599
13^1=13 = 13 mod 599
13^2=169 = 169 mod 599
13^3 = 2197 = 400 mod 599
13^4=28561 = 408 mod 588
13^5 = 512 mod 599
13^6 = 67 mod 599
13^7 = 272 mod 599
13^1031= 13^(6*171)*13^5
13^1031= ((67mod599)^171)*512mod599
13^1031= ((67mod599)^5)^34*(67mod599)*512mod599
13^1031= (72mod599)^34*(67*512mod599)
13^1031= (72mod599)^34*(161mod599)
13^1031= ((72mod599)^4)^8*(72mod599)^2*(161mod599)
13^1031= (320mod599)^8*(392mod599)*(161mod599)
13^1031= (320mod599)^3*(392mod599)^3*(320mod599)^2*(392mod599)*(161mod599)
13^1031= (304mod599)*(304mod599)*(570mod599)*(392*161mod599)
13^1031= ((304*304)mod599) * (570mod599)*(217mod599)
13^1031= (170)mod599 * (570*217)mod599
13^1031= (170)mod599 * (296)mod599
13^1031= (170*296)mod599
13^1031 = 4 mod 599
the answer is 4
Verification:
The EASY way of doing it!!!!!:
[13^1031] / 599 =0.0066777963 2721202003 3388981636 0601001669 4490818030.....[Fractional part x 599] =4 !!.
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}\)