Question

Which positive integers n, where 20 ≤ n ≤ 30, have primitive roots?

Answer 1

Let us give a solution using Group Theory.

Result: The multiplicative group Z_n* = { [a] in Z_n | g.c.d(a,n) = 1 } of invertible elements of Z_n is cyclic iff n=2 or 4 or p^k or 2p^k for some odd prime p.

Observe that |Z_n*| = (n) , where (n) is the Euler's totient function.
Now, Z_n* is cyclic iff there is an element in it of order (n) ( which generates Z_n* ).
In other words, Z_n* is cyclic iff there is an integer a such that gcd(a,n)=1 and the multiplicative order of a is (n) modulo n.
This is equivalent to saying that Z_n* is cyclic iff n has a primitive root.

Thus, a positive integer n has a primitive root iff Z_n* is cyclic iff n=2 or 4 or p^k or 2p^k for some odd prime p(using the result).

The positive integers n such that 20 n   30 which are one of the form p^k or 2p^k for some odd prime p are:::
22,23,25,26,27 and 29.

Hence, the positive integers n, where 20 n 30, which have primitive roots are 22,23,25,26,27 and 29.