Solving Modular Exponentiation: How Did My Friend Break Down 95937 mod 2537?

[Raza]

Homework Statement

95⁹³⁷ mod 2537

Homework Equations

None

The Attempt at a Solution

Here's what my friend did:

How do I do this? and how did he do this?

 

[eumyang]

$$95 \times 1786 \times 341 \times 2188 \times 403$$

How do I do this? and how did he do this?

This can't be right, because the product above ends with a 0. Powers of any number that ends with a 5 will also end with a 5 (except if the exponent is 0). In fact, for n >=5,
95ⁿ ends with "09375" if n is odd, and
95ⁿ ends with "90625" if n is even.

If found this through using Calculator in Windows 7.

Furthermore,

Here's what my friend did:
$$95^{937}$$

$$95 \times 240^{234}$$

This isn't right either. According to Calculator,
95⁹³⁷ ≈ 1.33 * 10¹⁸⁵³, but
95 * 240²³⁴ ≈ 8.85 * 10⁵⁵⁸.
(This assumes that there is no overflow error here.)

In fact, 95⁹³⁷ should equal 95 * (81450625)²³⁴.

Is the entire problem? Perhaps it should be 95⁹³⁷ mod some number?

 

[Raza]

removed

 

[Outlined]

what is the question exactly ?

 

[Raza]

how did my friend do it?
how did he break down the huge number?
'
basically
how do you compute 95⁹³⁷ mod 2537

 

[Outlined]

I see, well the answer is 1520 but I found that by using MAGMA. Do not know yet how to do it manually.

n := 2537;
R := ResidueClassRing(n);

number := R ! 95; 
number ^ 937;

http://magma.maths.usyd.edu.au/calc/

 

[Outlined]

What you could do is looking at the unit group of Z/2537Z. I found out it is isomorphic to Z/2Z x Z/1218Z however I used MAGMA too for this one.

Another trick (it seems your friend did something like that): break down Z/2537Z. You have (at least when it comes to addition) an isomorphism with Z/pZ x Z/qZ (do not confuse this with the isomorphism of the unit group). You can repeat that, it has to do with the Chinese Remainder theorem I think.

 

[Raza]

Okay, I had this question in my exam and after being verified by other people, I think I got it correct.
95⁹³⁷ mod 2537 = 95⁵¹² mod 2537 x 95²⁵⁶ mod 2537 x 95¹²⁸ mod 2537 x 95³² mod 2537 x 95⁸ mod 2537 x 95¹ mod 2537

So now you do the mod from the power of 1 at .
95¹ mod 2537 = 95
95² mod 2537 = 1414
95⁴ mod 2537 = (95²)² mod 2537 = 1414² mod 2537 = 240
95⁸ mod 2537 = (95⁴)² mod 2537 = 240² mod 2537 = 1786
95¹⁶ mod 2537 = (95⁸)² mod 2537 = 1786² mod 2537 = 787
95³² mod 2537 = (95¹⁶)² mod 2537 = 787² mod 2537 = 341
95⁶⁴ mod 2537 = (95³²)² mod 2537 = 341² mod 2537 = 2116
95¹²⁸ mod 2537 = (95⁶⁴)² mod 2537 = 2116² mod 2537 = 2188
95²⁵⁶ mod 2537 = (95¹²⁸)² mod 2537 = 2188² mod 2537 = 25
95⁵¹² mod 2537 = (95²⁵⁶)² mod 2537 = 25² mod 2537 = 625

From the first equation:
95⁹³⁷ mod 2537 = (625 x 25 x 2188 x 341 x 1786 x 95) mod 2537
95⁹³⁷ mod 2537 = (625 x 25) mod 2537 x (2188 x 341) mod 2537 x (1786 x 95) mod 2537
95⁹³⁷ mod 2537 = (403 x 230 x 2228) mod 2537 = 1520