A387331 Least k such that n*k + 1 is a prime > 2 with 2 as a primitive root; a(n) = 0 if no such k exists.

2, 1, 4, 1, 2, 2, 4, 0, 2, 1, 6, 1, 4, 2, 4, 0, 26, 1, 22, 3, 10, 3, 6, 0, 4, 2, 6, 1, 2, 2, 12, 0, 2, 13, 6, 1, 4, 11, 14, 0, 2, 5, 4, 15, 4, 3, 14, 0, 4, 2, 12, 1, 2, 3, 12, 0, 26, 1, 12, 1, 58, 6, 6, 0, 2, 1, 4, 9, 2, 3, 12, 0, 4, 2, 38, 25, 50, 7, 4, 0, 2

Offset: 1

Author

Pablo Cadena-Urzúa, Aug 26 2025

Keywords

• nonn
• new

Comments

If n is a multiple of 8 then a(n) = 0.

Proof: If n = 8*m, then any prime p = n*k+1 satisfies p == 1 (mod 8). Thus 2 is a quadratic residue modulo p, so ord_p(2) | (p-1)/2 and cannot equal p-1.

Computations show that for 1 <= n <= 2000 with 8 !| n, a(n) > 0. This agrees with Artin's conjecture: for each n with 8 !| n there should be infinitely many primes p == 1 (mod n) with 2 as a primitive root.

Examples

			a(1) = 2 since 1*2+1 = 3 is prime and 2 generates (Z/3Z)^*.
a(2) = 1 since 2*1+1 = 3 is prime and 2 is a primitive root modulo 3.
a(3) = 4 since 3*4+1 = 13 is prime and ord_13(2) = 12.
a(8) = 0 because every 8*k+1 == 1 (mod 8).
		

References

• E. Artin, Collected Papers, Addison-Wesley, 1965.

Links

• Pablo Cadena-Urzua, Table of n, a(n) for n = 1..2000

Crossrefs

Cf. A001122, A005596.

Programs

Maple

a := proc(n) local k, p;
  if n mod 8 = 0 then return 0 fi;
  for k from 1 do
    p := n*k+1;
    if isprime(p) and p>2 then
      if order(Mod(2, p)) = p-1 then return k fi;
    fi;
  od;
end;

Mathematica

a[n_] := If[Mod[n, 8]==0, 0, Module[{k=1, p, fac}, While[True,
  p=n*k+1;
  If[p>2 && PrimeQ[p], fac=FactorInteger[p-1][[All, 1]];
  If[And@@(PowerMod[2, (p-1)/#, p]!=1&/@fac), Return[k]]];
  k++]]]

Python

from sympy import isprime, factorint
def is_primitive_root_base2(p):
    phi = p-1
    return all(pow(2, phi//q, p)!=1 for q in factorint(phi))
def a(n, kmax=10**7):
    if n%8==0: return 0
    for k in range(1, kmax+1):
        p = n*k+1
        if p>2 and isprime(p) and is_primitive_root_base2(p):
            return k
    return 0

Formula

a(n) = 0 if n == 0 (mod 8).

Otherwise, a(n) = min { k >= 1 : p = n*k+1 is prime > 2 and ord_p(2) = p-1 }.