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.