A382220 Numbers k such that every primitive root mod k is prime.

3, 4, 5, 6, 7, 9, 10, 14, 18, 22, 54

Offset: 1

Author

Miles Englezou, Mar 18 2025

Keywords

• nonn
• more

Comments

There are no more terms up to k = 10^8.

Is this sequence finite? Since the number of primitive roots mod k is equal to phi(phi(k)), the size of the set of primitive roots generally increases with increasing k. Coupled with the fact that there are few restrictions regarding what kind of number can be a primitive root mod k (except, for example, that no square can be a primitive root), it becomes increasingly less likely that the set of primitive roots mod k will contain only primes as k increases. Furthermore, if the odd prime factor of k is congruent to 1 mod 4, then -g is a primitive root mod k if g is, a symmetry which further decreases the likelihood that every primitive root mod k is prime for large k.

Examples

			The primitive roots mod a(n) for 1 <= n <= 11:
  3  [2]
  4  [3]
  5  [2, 3]
  6  [5]
  7  [3, 5]
  9  [2, 5]
 10  [3, 7]
 14  [3, 5]
 18  [5, 11]
 22  [7, 13, 17, 19]
 54  [5, 11, 23, 29, 41, 47]
		

Crossrefs

Cf. A033948, A046147, A382224.

Programs

PARI

isok(n) = if((n==2 || n==4 || (n%4<>0 && isprimepower(n)<>0) || (n%4<>0 && n/2==floor(n/2) && isprimepower(n/2)<>0))==0, return(0), my(m=lcm(apply(f->(f[1]-1)*f[1]^(f[2]-1-(f[1]==2&&f[2]>2)), Vec(factor(n)~)))); for(k=1, n-1, if(gcd(k, n)==1 && znorder(Mod(k, n))==m && isprime(k)==0, return(0)); if(k==n-1, return(1))))