A055578 -id:A055578 - cp's OEIS frontend

A101710 Primes p for which the least-magnitude negative primitive root is not a primitive root of p^2. Like A055578, but for negative rather than positive primitive roots.

3, 11, 3511, 6692367337

Offset: 1

Bernard Leak (bernard(AT)brenda-arkle.demon.co.uk), Dec 13 2004

There is a rough heuristic suggesting that a prime p will occur in this list with probability 1/p; the actual density seen here tails off faster than that. No other primes with this property exist up to 2^36. Used for testing a multiprecision division algorithm.

The sequence giving the least-magnitude primitive roots r of primes p for which r is not a primitive root of p^2 begins -1,-3,-2,-5,..., with no other cases known up to 2^36.

			-3 is a primitive root of 11. That is, the successive powers of -3 work through all the nonzero residues modulo 11 before coming round through 1 to -3 again: -3, -2, -5, 4, -1, 3, 2, 5, -4, 1, -3, ...
-3 also happens to be the negative number of least magnitude with this property (-1 obviously fails, -2 yields -2, 4, 3, 5, 1, -2 ...) Modulo 11^2 = 121, however, successive powers of -3 do not yield all the corresponding residues (that is, all the ones which aren't multiples of 11): we only get -3, 9, -27, 81, -1, 3, -9, 27, -81, 1, -3, ...

Cf. A055578, A060503. A060504.

A134307 Primes p such that A^(p-1) == 1 (mod p^2) for some A in the range 2 <= A <= p-1.

Original entry on oeis.org

11, 29, 37, 43, 59, 71, 79, 97, 103, 109, 113, 127, 131, 137, 151, 163, 181, 191, 197, 199, 211, 223, 229, 233, 241, 257, 263, 269, 281, 283, 293, 307, 313, 331, 347, 349, 353, 359, 367, 373, 379, 397, 401, 419, 421, 433, 439, 449, 461, 463, 487, 499, 509

Offset: 1

Joerg Arndt, Aug 27 2008

nonn

It's worth observing that there are p-1 elements of order dividing p-1 modulo p^2 that are of the form r^(k*p) mod p^2 where r is a primitive element modulo p and k=0,1,...,p-2. Heuristically, one can expect that at least one of them belongs to the interval [2,p-1] with probability about 1 - (1 - 1/p)^(p-1) ~= 1 - 1/e.
Numerically, among the primes below 1000 (out of the total number pi(1000)=168) there are 103 terms of the sequence, and the ratio 103/168 = 0.613 which is already somewhat close to 1-1/e ~= 0.632.
If we replace p^2 with p^3, heuristically it is likely that the sequence is finite (since 1 - (1 - 1/p^2)^(p-1) tends to 0 as p grows). - Max Alekseyev, Jan 09 2009
Replacing p^2 with p^3 gives just the one term (113) for p < 10^6. - Joerg Arndt, Jan 07 2011
If furthermore the number A can be taken to be a primitive root modulo p, i.e., A is a generator of (Z/pZ)*, then that p belongs to A060503. - Jeppe Stig Nielsen, Jul 31 2015
The number of terms not exceeding prime(10^k), for k=1,2,..., are 2, 55, 652, 6303, 63219, ... - Amiram Eldar, May 08 2021

			Examples (pairs [p, A]):
[11, 3]
[11, 9]
[29, 14]
[37, 18]
[43, 19]
[59, 53]
[71, 11]
[71, 26]
[79, 31]
[97, 53]

L. E. Dickson, History of the theory of numbers, vol. 1, p. 105.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)
Wilfrid Keller and Jörg Richstein Fermat quotients that are divisible by p.

Cf. A001220, A055578, A039678, A143548, A222184, A060503.

Select[ Prime[ Range[100]], Product[ (PowerMod[a, # - 1, #^2] - 1), {a, 2, # - 1}] == 0 &] (* Jonathan Sondow, Feb 11 2013 *)

{ forprime (p=2, 1000,
   for (a=2, p-1, p2 = p^2;
     if( Mod(a, p2)^(p-1) == Mod(1, p2), print1(p, ", ") ;break() );
  ); ); }

A060503 Primes p that have a primitive root between 0 and p that is not a primitive root of p^2.

Original entry on oeis.org

2, 29, 37, 43, 71, 103, 109, 113, 131, 181, 191, 211, 257, 263, 269, 283, 349, 353, 359, 367, 373, 397, 439, 449, 461, 487, 509, 563, 599, 617, 619, 631, 641, 647, 653, 701, 739, 743, 773, 797, 839, 857, 863, 883, 887, 907, 919, 947, 971, 983, 1019, 1031

Offset: 1

Jud McCranie, Mar 22 2001

nonn

The smallest primitive roots of p that are not primitive roots of p^2 are in A060504.

Except for the initial term 2, this is a subsequence of A134307. - Jeppe Stig Nielsen, Jul 31 2015

			14 is a primitive root of 29 but not of 29^2, so 29 is a term.

Robert Israel, Table of n, a(n) for n = 1..1000

Cf. A055578, A060504, A134307.

filter:= proc(p) local x;
  if not isprime(p) then return false fi;
  x:= 0;
  do
    x:= numtheory:-primroot(x,p);
    if x = FAIL then return false fi;
    if x &^ (p-1) mod p^2 = 1 then return true fi;
  od
end proc:
select(filter, [2, seq(i,i=3..2000,2)]); # Robert Israel, Dec 01 2016

Reap[For[p = 2, p < 1100, p = NextPrime[p], prp = PrimitiveRootList[p]; prp2 = Select[PrimitiveRootList[p^2], # <= Last[prp]&]; If[AnyTrue[prp, FreeQ[prp2, #]&], Print[p]; Sow[p]]]][[2, 1]] (* Jean-François Alcover, Feb 26 2019 *)

forprime(p=2,,for(a=1,p-1,if(znorder(Mod(a,p))==p-1&Mod(a,p^2)^(p-1)==1,print1(p,", ");break()))) \\ Jeppe Stig Nielsen, Jul 31 2015

A127807 Least positive primitive root of (n-th prime)^2.

Original entry on oeis.org

3, 2, 2, 3, 2, 2, 3, 2, 5, 2, 3, 2, 6, 3, 5, 2, 2, 2, 2, 7, 5, 3, 2, 3, 5, 2, 5, 2, 6, 3, 3, 2, 3, 2, 2, 6, 5, 2, 5, 2, 2, 2, 19, 5, 2, 3, 2, 3, 2, 6, 3, 7, 7, 6, 3, 5, 2, 6, 5, 3, 3, 2, 5, 17, 10, 2, 3, 10, 2, 2, 3, 7, 6, 2, 2, 5, 2, 5, 3, 21, 2, 2, 7, 5, 15, 2, 3, 13, 2, 3, 2, 13, 3, 2, 7, 5, 2, 3, 2, 2

Offset: 1

Artur Jasinski, Jan 29 2007

A055578 lists the indices n such that a(n) differs from A001918(n).

D. Cohen, R. W. K. Odoni, and W. W. Stothers, On the Least Primitive Root Modulo p^2, Bulletin of the London Mathematical Society 6:1 (March 1974), pp. 42-46.

Bryce Kerr, Kevin McGown, and Tim Trudgian, The least primitive root modulo p^2. arXiv:1908.11497 [math.NT]

Cf. A001918, A127808, A127809, A127810.

<< NumberTheory`NumberTheoryFunctions` Table[PrimitiveRoot[(Prime[n])^2], {n, 1, 100}]
PrimitiveRoot[Prime[Range[100]]^2] (* Harvey P. Dale, Aug 19 2017 *)

Cohen, Odoni, & Stothers prove that a(n) < prime(n)^(1/4 + e) for any e > 0 and all large enough n. Kerr, McGown, & Trudgian give an effective version: a(n) < prime(n)^0.99 for all n. - Charles R Greathouse IV, Apr 28 2020

A060504 Let p be a prime that has a primitive root between 0 and p that is not also a primitive root of p^2 (A060503); sequence gives smallest such primitive root.

Original entry on oeis.org

1, 14, 18, 19, 11, 43, 96, 68, 111, 78, 176, 165, 48, 79, 171, 147, 317, 14, 257, 159, 242, 175, 194, 210, 52, 10, 250, 486, 559, 556, 286, 534, 340, 526, 84, 375, 168, 467, 392, 446, 667, 682, 13, 657, 292, 127, 457, 208, 296, 419, 705, 158, 806, 508, 617

Offset: 0

Jud McCranie, Mar 22 2001

nonn

			14 is a primitive root of 29 but not of 29^2.

Cf. A055578, A060503.

A060518 Primes p that have exactly two primitive roots that are not primitive roots mod p^2.

Original entry on oeis.org

367, 863, 907, 1327, 1549, 1579, 1607, 1619, 1697, 2221, 2267, 2551, 2671, 2677, 2693, 2719, 2837, 3209, 3313, 4049, 4373, 4391, 4909, 5261, 5669, 5693, 6007, 6269, 6343, 6547, 6653, 6703, 6857, 6907, 7013, 7559, 7573, 7583, 7669, 7723, 7919

Offset: 1

Jud McCranie, Mar 24 2001

nonn

If x is a primitive root mod prime p then either x is a primitive root mod p^2 or x has order p-1 mod p^2.

			159 and 205 are primitive roots mod 367, but not mod 367^2.

Cf. A060503, A055578, A060519, A060520.

A060519 Primes p that have exactly three primitive roots that are not primitive roots mod p^2.

Original entry on oeis.org

1103, 6569, 13187, 14939, 15313, 16649, 18587, 22091, 22769, 25163, 26189, 26759, 32069, 32647, 33289, 34381, 34939, 37397, 38459, 39047, 42863, 47189, 47699, 54011, 54139, 57173, 57527, 57923, 59539, 61553, 63311, 63347, 63467

Offset: 1

Jud McCranie, Mar 24 2001

nonn

If x is a primitive root mod prime p then either x is a primitive root mod p^2 or x has order p-1 mod p^2.

			284, 793 and 1054 are primitive roots mod 1103, but not mod 1103^2.

Cf. A060503, A055578, A060518, A060520.

A060520 Primes p that have at least four primitive roots that are not primitive roots mod p^2.

Original entry on oeis.org

653, 16631, 40487, 50033, 52517, 67631, 80803, 138107, 145253, 147197

Offset: 1

Jud McCranie, Mar 24 2001

40487 is unusual - it has four primitive roots with this property (5, 5^3, 5^5, 4492) and 5 is the least positive primitive root mod 40487 - see A055578.

			13425, 18243, 34196, 38462, 39362 and 51787 are primitive roots mod 52517, but not mod 52517^2.

Cf. A060503, A055578, A060518, A060519.

A305332 Multiplicative order of 5 (mod A123692(n)^2).

Original entry on oeis.org

1, 10385, 40486, 13367790, 1645333506, 6692367336, 11796759175

Offset: 1

Felix Fröhlich, May 30 2018

From Eric Chen, Jun 07 2018: (Start)
    b    known Wieferich primes in base b (multiplicative order of b mod these primes (also these primes^2)) (if the order is p-1, then b is a primitive root to mod this prime (but not mod this prime^2), see A055578)
  1093 (364), 3511 (1755)
  11 (5), 1006003 (1006002)
  1093 (182), 3511 (1755)
  2 (1), 20771 (10385), 40487 (40486), 53471161 (13367790), 1645333507 (1645333506), 6692367337 (6692367336), 188748146801 (11796759175)
  66161 (66160), 534851 (106970), 3152573 (788143)
  5 (4), 491531 (245765)
  3 (2), 1093 (364), 3511 (585)
  2 (1), 11 (5), 1006003 (503001)
  3 (1), 487 (486), 56598313 (56598312)
  71 (70)
  2693 (2692), 123653 (123652)
  2 (1), 863 (862), 1747591 (873795)
  29 (28), 353 (352), 7596952219 (7596952218)
  29131 (29130), 119327070011 (59663535005)
  1093 (91), 3511 (1755)
  2 (1), 3 (2), 46021 (7670), 48947 (24473), 478225523351 (478225523350)
  5 (4), 7 (3), 37 (36), 331 (110), 33923 (33922), 1284043 (428014)
  3 (1), 7 (6), 13 (12), 43 (42), 137 (68), 63061489 (63061488)
  281 (140), 46457 (46456), 9377747 (9377746), 122959073 (122959072)
  2 (1)
  13 (3), 673 (224), 1595813 (797906), 492366587 (246183293), 9809862296159 (44999368331)
  13 (6), 2481757 (827252), 13703077 (13703076), 15546404183 (7773202091), 2549536629329 (2549536629328)
  5 (2), 25633 (6408)
These orders n will satisfy that Phi_n(b) is divisible by p^2, where Phi is the cyclotomic polynomial. (Usually, Phi_n(b) is squarefree, but these are all exceptions; i.e., if p^2 divides Phi_n(b) (except the case p = 2, n = 2 and b == 3 (mod 4)), then p is a Wieferich prime in base b.)
(End)

Cf. A123692, A211241, A305331, A305333.

v=[2, 20771, 40487, 53471161, 1645333507, 6692367337, 188748146801]; for(k=1, #v, print1(znorder(Mod(5, v[k]^2)), ", "))

a(n) = A305331(A123692(n)).

A317706 Irregular triangle of numbers k < p^2 such that k is a primitive root modulo p but not p^2, p = prime(n).

Original entry on oeis.org

1, 8, 7, 18, 19, 31, 40, 94, 112, 118, 19, 80, 89, 150, 40, 65, 75, 131, 158, 214, 224, 249, 116, 127, 262, 299, 307, 333, 28, 42, 63, 130, 195, 263, 274, 352, 359, 411, 14, 60, 137, 221, 374, 416, 425, 467, 620, 704, 781, 827, 115, 117, 145, 229, 414, 513, 623, 726

Offset: 1

Jianing Song, Aug 05 2018

Also row n lists numbers k < p^2 such that the multiplicative order of k modulo p^2 is p - 1.
Row n has phi(prime(n) - 1) = A008330(n) terms.
Row sum is congruent to mu(prime(n) - 1) = A089451(n) modulo prime(n)^2, where mu is the Moebius function. For n >= 3, the product of n-th row is congruent to 1 modulo prime(n)^2.
Does every integer appear in this sequence? For example, 3 does not appear until the prime 1006003 and 5 does not appear until the prime 40487. Where does 2 first appear?

			(2)   1,
(3)   8,
(5)   7, 18,
(7)   19, 31,
(11)  40, 94, 112, 118,
(13)  19, 80, 89, 150,
(17)  40, 65, 75, 131, 158, 214, 224, 249,
(19)  116, 127, 262, 299, 307, 333,
(23)  28, 42, 63, 130, 195, 263, 274, 352, 359, 411,

Cf. A008330, A055578, A089451, A143548.

Table[Select[Range[p^2 - 1], MultiplicativeOrder[#, p^2] == p - 1 &], {p, Prime@ Range@ 11}] // Flatten (* Michael De Vlieger, Aug 05 2018 *)

forprime(p=2,100,for(i=1,p^2,if(Mod(i,p)!=0,if(znorder(Mod(i,p^2))==p-1,print1(i, ", ")))))

cp's OEIS Frontend

A101710 Primes p for which the least-magnitude negative primitive root is not a primitive root of p^2. Like A055578, but for negative rather than positive primitive roots.

Views

Author

Keywords

Comments

Examples

Crossrefs

A134307 Primes p such that A^(p-1) == 1 (mod p^2) for some A in the range 2 <= A <= p-1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

A060503 Primes p that have a primitive root between 0 and p that is not a primitive root of p^2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A127807 Least positive primitive root of (n-th prime)^2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

A060504 Let p be a prime that has a primitive root between 0 and p that is not also a primitive root of p^2 (A060503); sequence gives smallest such primitive root.

Views

Author

Keywords

Examples

Crossrefs

A060518 Primes p that have exactly two primitive roots that are not primitive roots mod p^2.

Views

Author

Keywords

Comments

Examples

Crossrefs

A060519 Primes p that have exactly three primitive roots that are not primitive roots mod p^2.

Views

Author

Keywords

Comments

Examples

Crossrefs

A060520 Primes p that have at least four primitive roots that are not primitive roots mod p^2.

Views

Author

Keywords

Comments

Examples

Crossrefs

A305332 Multiplicative order of 5 (mod A123692(n)^2).

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Formula

A317706 Irregular triangle of numbers k < p^2 such that k is a primitive root modulo p but not p^2, p = prime(n).