+0  
 
0
107
5
avatar

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

Guest Feb 14, 2017

Best Answer 

 #2
avatar+18609 
+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

heureka  Feb 14, 2017
Sort: 

5+0 Answers

 #1
avatar+8763 
+5

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

 

Omi67  Feb 14, 2017
 #2
avatar+18609 
+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+90546 
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

Melody  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 !!.

Guest Feb 14, 2017
 #5
avatar+18609 
+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

heureka  Feb 15, 2017
edited by heureka  Feb 15, 2017

9 Online Users

We use cookies to personalise content and ads, to provide social media features and to analyse our traffic. We also share information about your use of our site with our social media, advertising and analytics partners.  See details