1. ## order

Hi,

Find the order of 3 modulo 97.

That is, find the smallest positve integer x such that 3^x = 1 mod 97.

Using a calculator, I found the answer to be x = 48, but I want to know how to do this without a calculator.

Let phi(n) be Euler's phi function.
I know by Euler's Theorem that 3^(phi(97)) = 1 mod 97, and since 97 is prime, I know phi(97) = 96.

48 = 96/2, but I don't see how to show that 48 is the order from this. Any help would be awesome. Thanks.

2. Originally Posted by jimmyjimmyjimmy
Hi,

Find the order of 3 modulo 97.

That is, find the smallest positve integer x such that 3^x = 1 mod 97.

Using a calculator, I found the answer to be x = 48, but I want to know how to do this without a calculator.

Let phi(n) be Euler's phi function.
I know by Euler's Theorem that 3^(phi(97)) = 1 mod 97, and since 97 is prime, I know phi(97) = 96.

48 = 96/2, but I don't see how to show that 48 is the order from this. Any help would be awesome. Thanks.
Well, if $3^x= 1$ (mod 97), then $(3^x)^n= 1$ (mod 97) for any n. That is, knowing that $3^{phi(97)}= 3^{96}= 1$ (mod 97) tells you that the lowest power must be some divisor of 96. You would still have to show that $3^2$ $3^3$, $3^4$, $3^6$, through all divisors of 96 less than 48 are NOT congurent to 1 mod 97.