Hakob asked in Science & MathematicsMathematics · 7 years ago

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
• 7 years ago

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.

• 7 years ago

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.