+0  
 
0
363
17
avatar

64^235 mod 391

Guest Feb 4, 2015
Sort: 

17+0 Answers

 #1
avatar+91045 
+5

I just entered this into the calc

mod(64^235,391)

 

$$\left({{\mathtt{64}}}^{{\mathtt{235}}}\right) {mod} \left({\mathtt{391}}\right) = {\mathtt{4}}$$

 

I don't know how to do this without the calc  

Melody  Feb 4, 2015
 #2
avatar+78741 
+10

Notice the pattern, Melody

64^15 mod 391  = 4

64^59mod 391 = 4

64^103mod 391 = 4

Which leads us to believe that this pattern repeats every 44th power

Therefore

64^(15 + 44n)mod 391 = 4 for all positive integers, n

So

64^(15 + 44*5)mod 391  = 64^(15 + 220)mod 391 = 64^(235)mod 391  = 4 ....!!!

 

CPhill  Feb 4, 2015
 #3
avatar+4155 
0

uh oh did melody just get schooled by chris....?

zegroes  Feb 4, 2015
 #4
avatar+78741 
0

Actually, zegroes, there was some "brute force" required in my answer.....I just thought it was an interesting pattern......LOL!!!

 

CPhill  Feb 4, 2015
 #5
avatar+4155 
0

its ok chris you can admit it i mean its only right the dinosaur gets school by the much wiser(OLDER) person here aka the Fossil!

zegroes  Feb 4, 2015
 #6
avatar+78741 
0

LOL!!!

 

CPhill  Feb 4, 2015
 #7
avatar+18715 
+10

64^235 mod 391

$$\small{\text{
$
\begin{array}{ll}
64^{235} \mod 391\\
=(64^5)^{47}\mod 391 &\quad | \quad (64^5) \mod 391 = 302 \\
= (302)^{47}\mod 391 \\
= 302^2 *(302)^{45}\mod 391 \\
= 302^2 *(302^3)^{15}\mod 391 &\quad | \quad (302^3) \mod 391 = 4 \\
= 302^2*4^{15}\mod 391\\
= 302^2*(4^3)^{5} \mod 391 &\quad | \quad 4^3= 64 \\
=302^2*(64)^5 \mod 391 &\quad | \quad (64^5) \mod 391 = 302 \\
=302^2*302 \mod 391\\
=302^3 \mod 391 &\quad | \quad (302^3) \mod 391 = 4 \\
= 4 \mod 391
\end{array}
$
}}$$

heureka  Feb 5, 2015
 #8
avatar+91045 
+3

Thanks Heureka, I'll try and remember that.  :) 

Thanks Chris but I think Heureka's makes mores sense. :))

Melody  Feb 5, 2015
 #9
avatar+91045 
+8

I have tucked this one away in "reference material"  

Melody  Feb 5, 2015
 #10
avatar+78741 
0

It's just a different approach....whether it "makes more sense" is debatable....

I think that mine is perfectly valid....

 

CPhill  Feb 5, 2015
 #11
avatar+18715 
+10

See:

Square-and-Multiply-Algorithm with modulo for any $$\small{\text{$b^x\mod n$}}$$

heureka  Feb 5, 2015
 #12
avatar+91045 
0

Is that meant to take me somewhere Heureka??

Melody  Feb 5, 2015
 #14
avatar+91045 
0

Thanks Heureka 

Melody  Feb 5, 2015
 #15
avatar+18715 
+5

long modulo( long b, long x, long n) { // b = basic, x = exponent, n = modulo

   long z=1; b=b % n;

   while (x !=0) {

      if (x%2 !=0) z = (z*b)%n; // Exponent odd

      b =(b*b)% n; x = x/2;

  } // while

  return z;

}

heureka  Feb 5, 2015
 #16
avatar+18715 
+5

Square and Multiply Algorithm:

 

$$64^{235} \mod{391}$$

 

$$\small{\text{
$
\begin{array}{lr}
Exponent&z=1\\
&64 \mod 391 = 64 = b\\
\hline
235\ odd: &\underbrace{1*64}_{=z*b} \mod 391 = 64 = z\\
&(\underbrace{64}_{=b})^2 \mod 391 = 186 = b \\
:2 & \\
\hline
117\ odd: &\underbrace{64*186}_{=z*b} \mod 391 = 174 = z\\
&(\underbrace{186}_{=b})^2 \mod 391 = 188 = b \\
:2 & \\
\hline
58\ even: &(\underbrace{188}_{=b})^2 \mod 391 = 154 = b \\
:2 & \\
\hline
29\ odd: &\underbrace{174*154}_{=z*b} \mod 391 = 208 = z\\
&(\underbrace{154}_{=b})^2 \mod 391 = 256 = b \\
:2 & \\
\hline
14\ even: &(\underbrace{256}_{=b})^2 \mod 391 = 239= b \\
:2 & \\
\hline
7\ odd: &\underbrace{208*239}_{=z*b} \mod 391= 55= z\\
&(\underbrace{239}_{=b})^2 \mod 391 = 35= b \\
:2 & \\
\hline
3\ odd: &\underbrace{55*35}_{=z*b} \mod 391= 361 = z\\
&(\underbrace{35}_{=b})^2 \mod 391 = 52= b \\
:2 & \\
\hline
1\ odd: &\underbrace{361*52}_{=z*b} \mod 391= \textcolor[rgb]{1,0,0}{4} = z\\
&(\underbrace{52}_{=b})^2 \mod 391= 358= b \\
:2 & \\
0\ end
\end{array}
$
}}$$

heureka  Feb 5, 2015
 #17
avatar+91045 
0

Thanks once agaain Heureka 

Melody  Feb 5, 2015

8 Online Users

avatar
avatar
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