+0  
 
0
745
5
avatar

What is the remainder of: 13^1031 mod 599 =? Thanks for help.

 Feb 14, 2017

Best Answer 

 #2
avatar+26364 
+15

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}\)

 

laugh

 Feb 14, 2017
 #1
avatar+12525 
+5

What is the remainder of: 13^1031 mod 599 =? Thanks for help.

 

 Feb 14, 2017
 #2
avatar+26364 
+15
Best Answer

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}\)

 

laugh

heureka Feb 14, 2017
 #3
avatar+118587 
0

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      laugh

 

 

 

the answer is 4

Verification:

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

 Feb 14, 2017
 #4
avatar
0

The EASY way of doing it!!!!!:

 

[13^1031] / 599 =0.0066777963 2721202003 3388981636 0601001669 4490818030.....[Fractional part x 599] =4 !!.

 Feb 14, 2017
 #5
avatar+26364 
+10

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}\)

 

laugh

 Feb 15, 2017
edited by heureka  Feb 15, 2017

4 Online Users

avatar