# Notice that 60 = 2^2 * 3 * 5. Explain why it is true that if 7^(30), 7^(20) and 7^(12) are not congruent to?

Notice that 60 = 2^2 * 3 * 5. Explain why it is true that if 7^(30), 7^(20) and 7^(12) are not congruent to 1 mod 61, then 7 is a primitive root mod 61. (Start by supposing that 7 has order e mod 61. What do you know about the order e?)

Relevance

The key here is that any proper divisor of 60 divides either 30, 20 or 12 (possibly more than one). You can verify for yourself - the proper divisors of 60 are 1,2,3,4,5,6,10,12,15,20,30.

We know that 7^e = 1 (mod 61). Our goal is to prove that e = 60, and we'll do this by contradiction.

Suppose that e is not 60. By Fermat's Little Theorem, 7^60 = 1 (mod 61). Hence e must be a proper divisor of 60. Therefore, by the above, it must divide 30, 20 or 12. Suppose it divides 30. Then there is an integer k such that e*k = 60. Therefore,

7^30 = 7^(e*k) = (7^e)^k = 1^k = 1 (mod 61)

which is a contradiction. We get a similar contradiction if e divides 20 or 12.

Thus e does not divide 30, 20 or 12. Therefore, it is not a proper divisor of 60, so therefore e = 60.

Hence, 7 is a primitive root mod 61.

• If p is a prime, the order of any nonzero element mod p must divide p - 1.

So if e denotes the order of 7 mod 61, e must divide 61 - 1 = 60.

So e must be one of the numbers 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60.

If e were 1, 2, 4, 6, or 12, this would imply that 7^1, 7^2, 7^4, 7^6, or 7^12 were 1 mod 61, and this would imply that (7^1)^12, (7^2)^6, (7^4)^3, (7^6)^2, or (7^12)^1 would be 1 mod 61, so in any of these cases we would actually see that 7^12 = 1 mod 61.

Similarly, if e were 5, 10 or 20, we would have that 7^20 = 1 mod 61.

And if e were 15 or 30, then we would have 7^30 = 1 mod 61.

So if none of 7^12, 7^20, 7^30 is 1 mod 61, the only possible value left for e is 60. And this would mean that 7 is a generator.

[None of this analysis really depends on 7 being 7, of course. It's the same check for any nonzero element c mod 61: to see if it's a generator, it's enough to check that none of c^12, c^20, and c^30 are congruent to 1 mod 61.]

As it happens, none of 7^12, 7^20, and 7^30 are congruent to 1 mod 61, so 7 is indeed a generator.