A397854 Smallest positive integer that is a primitive root modulo p but not modulo p^2, where p = prime(n).

1, 8, 7, 19, 40, 19, 40, 116, 28, 14, 115, 18, 313, 19, 67, 338, 506, 498, 279, 11, 306, 147, 269, 184, 107, 248, 43, 317, 96, 68, 497, 111, 161, 328, 313, 559, 226, 266, 253, 259, 532, 78, 176, 813, 349, 1312, 165, 644, 1203, 236, 694, 410, 1106, 394, 48, 79, 171

Offset

1,2

Comments

a(n) is the smallest term in row n of A317706.

Equivalently, a(n) is the least primitive root k modulo p = prime(n) such that k^(p-1) == 1 (mod p^2); that is, the least primitive root modulo p to which p is a Wieferich prime.

No perfect square occurs as a value, since a square is never a primitive root of an odd prime. Apparently the only perfect power that occurs, other than a(1) = 1, is a(2) = 8.

It appears that every positive integer that is not a perfect power occurs in the sequence. The value 2 does not occur for any prime below 2^64; the value 3 first occurs at the prime 1006003, the value 5 at 40487, and the value 6 at 66161.

Links

Daniel Okwor, Table of n, a(n) for n = 1..1007

Example

For n = 2, p = 3: 2 and 5 are primitive roots modulo 3 that are also primitive roots modulo 9, but 8 is a primitive root modulo 3 (8 == 2 (mod 3)) and not modulo 9, since 8^2 = 64 == 1 (mod 9). As 8 is the smallest such k, a(2) = 8.

Prog

(PARI) a(n) = my(p=prime(n)); for(k=1, oo, if(gcd(k, p)==1 && znorder(Mod(k, p))==p-1 && Mod(k, p^2)^(p-1)==1, return(k)));
(Python)
from sympy import prime, n_order
from math import gcd
def a(n):
    p = prime(n); k = 1
    while not (gcd(k, p)==1 and n_order(k, p)==p-1 and pow(k, p-1, p*p)==1): k += 1
    return k

Crossrefs

Cf. A317706, A001918, A127807, A039678, A055578, A101710, A060503, A008330, A000040.

Sequence in context: A075573 A317706 A302677 * A304267 A166138 A348673

Adjacent sequences: A397849 A397851 A397852 * A397855 A397856 A397857

Keyword

nonn,easy,new

Author

Daniel Okwor and Eric Chen, Jul 12 2026

Status

approved