A060503 -id:A060503 - cp's OEIS frontend

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.

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.

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() );
  ); ); }

A055578 "Non-generous primes": primes p whose least positive primitive root is not a primitive root of p^2.

Original entry on oeis.org

2, 40487, 6692367337

Offset: 1

Bernard Leak (bernard(AT)brenda-arkle.demon.co.uk), Aug 24 2000

For r a primitive root of a prime p, r + qp is a primitive root of p: but r + qp is also a primitive root of p^2, except for q in some unique residue class modulo p. In the exceptional case, r + qp has order p-1 modulo p^2 (Burton, section 8.3).
No other terms below 10^12 (Paszkiewicz, 2009).
Each term p is a Wieferich prime to base A046145(p). For example, a(2) and a(3) are base-5 Wieferich (see A123692). - Jeppe Stig Nielsen, Mar 06 2020

David Burton, Elementary Number Theory, Allyn and Bacon, Boston, 1976, first edition (cf. Section 8.3).

Joerg Arndt, Matters Computational (The Fxtbook), section 39.7.2, p.780.
Stephen Glasby, Three questions about the density of certain primes, Posting to Number Theory List (NMBRTHRY(AT)LISTSERV.NODAK.EDU), Apr 22, 2001.
Bryce Kerr, Kevin McGown, Tim Trudgian, The least primitive root modulo p^2, arXiv:1908.11497 [math.NT], 2019.
A. Paszkiewicz, A new prime for which the least primitive root (mod p) and the least primitive root (mod p^2) are not equal, Math. Comp. 78 (2009), 1193-1195.

Cf. A060503, A060504.

Select[Prime@Range[7!], ! PrimitiveRoot[#] == PrimitiveRoot[#^2] &] (* Arkadiusz Wesolowski, Sep 06 2012 *)

Prime A000040(n) is in this sequence iff A001918(n)^(A000040(n)-1) == 1 (mod A000040(n)^2).

Prime A000040(n) is in this sequence iff A001918(n) differs from A127807(n).

a(3) from Stephen Glasby (Stephen.Glasby(AT)cwu.EDU), Apr 22 2001

Edited by Max Alekseyev, Nov 10 2011

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.

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.

Original entry on oeis.org

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.

cp's OEIS Frontend

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

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

A055578 "Non-generous primes": primes p whose least positive primitive root is not a primitive root of p^2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

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