Find all incongruent integers having order 10 mod 61Solution

Find all incongruent integers having order 10 mod 61?

Solution

By the Primitive Root Theorem, 61 has a primitive root and U(61) is cyclic. We could find a generator of U(61) to find a generator, and then look at r^6, which will have order 10. Any element of order 10 generates a group of index 6 in U(61), which, since 61 is prime, has order 60. And since this multiplicative group is cyclic, that subgroup is unique and all elements of order 10 will be in it.

I don\'t know an easy way to find an element with order 10, but I have a spreadsheet that analyzes U(n) for me, and I see that 3 has order 10. 3^10 = 59049 = 1 mod 61. You verify that no smaller power does. You only have to check 3^2 and 3^5 since the power has to divide 10.

So the elements of order 10 must be among 3^i for i = 1 to 9. Let\'s look at those and their order.
3 has order 10
3^2 has order 5 (since 2x5=10)
3^3 = 27 has order 10
3^4 has order 5 (since 4x5 is a multiple of 10)
3^5 has order 2
3^6 has order 5
3^7 has order 10
3^8 has order 5
3^9 has order 10
So the only ones with order 10 are:
3
3^2 = 27
3^7 = 52 mod 61 and
3^9 = 41