Hello everyone I am a computer science student, I am studying the Algorithms course independently.

During the course I saw this question: I think it's a simple question, but I can not understand it

Prove or disprove: 5^{3001} = 12^{301} (mod 31)$

my plan to solve it is starting with (5 and 12) and squaring repeatedly modulo 31.

my solution:

5^{3001} = 12^{301} (mod 31) =
5*5^{3000} = 12*12^{300} (mod 31) =
5*125^{2998} = 12*6^{300}*2^{300} (mod 31) = 
5*1^{2998} = 12*36^{299}*32^{296} (mod 31) = 
5 = 12*36^{299}*32^{296} (mod 31) = 
5 = 12*5^{299}*1^{296} (mod 31) = 
5 = 12*125^{297}*1 (mod 31) = 
5 = 12*1^{297}*1 (mod 31) = 
5 = 12

That's what I did, I do not think it is right to do so, is there another way to prove or disprove the claim?

CodePudding user response：

Exponentiation by squaring works of course, it is OK to do, but it looks like a lot of work and you can use a shortcut: a³⁰ ≡ 1 mod 31 if gcd(a, 31) = 1 (Euler's theorem).

5³⁰⁰¹ ≡ 5 * (5³⁰)¹⁰⁰ ≡ 5 * 1¹⁰⁰ ≡ 5 mod 31

12³⁰¹ ≡ 12 * (12³⁰)¹⁰ ≡ 12 * 1¹⁰ ≡ 12 mod 31

The exponents 3001 and 301 (in combination with the modulus, 31) look like they were chosen specifically to enable an approach based on Euler's theorem. For most arbitrary numbers that could have been chosen, this approach wouldn't have been so nice.