+0

# 64^235 mod 391

0
431
17

64^235 mod 391

Guest Feb 4, 2015

#13
+18827
+10
heureka  Feb 5, 2015
Sort:

#1
+91404
+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
+80774
+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
+4145
0

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

zegroes  Feb 4, 2015
#4
+80774
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
+4145
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
+80774
0

LOL!!!

CPhill  Feb 4, 2015
#7
+18827
+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
+91404
+3

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

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

Melody  Feb 5, 2015
#9
+91404
+8

I have tucked this one away in "reference material"

Melody  Feb 5, 2015
#10
+80774
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
+18827
+10

See:

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

heureka  Feb 5, 2015
#12
+91404
0

Is that meant to take me somewhere Heureka??

Melody  Feb 5, 2015
#14
+91404
0

Thanks Heureka

Melody  Feb 5, 2015
#15
+18827
+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
+18827
+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= {4} = z\\ &(\underbrace{52}_{=b})^2 \mod 391= 358= b \\ :2 & \\ 0\ end \end{array}  }}$$

heureka  Feb 5, 2015
#17
+91404
0

Thanks once agaain Heureka

Melody  Feb 5, 2015

### 4 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