cp's OEIS Frontend

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

%I A382220 #17 Mar 21 2025 10:12:21
%S A382220 3,4,5,6,7,9,10,14,18,22,54
%N A382220 Numbers k such that every primitive root mod k is prime.
%C A382220 There are no more terms up to k = 10^8.
%C A382220 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.
%e A382220 The primitive roots mod a(n) for 1 <= n <= 11:
%e A382220   3  [2]
%e A382220   4  [3]
%e A382220   5  [2, 3]
%e A382220   6  [5]
%e A382220   7  [3, 5]
%e A382220   9  [2, 5]
%e A382220  10  [3, 7]
%e A382220  14  [3, 5]
%e A382220  18  [5, 11]
%e A382220  22  [7, 13, 17, 19]
%e A382220  54  [5, 11, 23, 29, 41, 47]
%o A382220 (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))))
%Y A382220 Cf. A033948, A046147, A382224.
%K A382220 nonn,more
%O A382220 1,1
%A A382220 _Miles Englezou_, Mar 18 2025