Remainder.

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 =? Thanks for help.

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:

http://ptrow.com/perl/calculator.pl

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}$