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.