cp's OEIS Frontend

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

%I A134307 #41 May 08 2021 08:32:55
%S A134307 11,29,37,43,59,71,79,97,103,109,113,127,131,137,151,163,181,191,197,
%T A134307 199,211,223,229,233,241,257,263,269,281,283,293,307,313,331,347,349,
%U A134307 353,359,367,373,379,397,401,419,421,433,439,449,461,463,487,499,509
%N A134307 Primes p such that A^(p-1) == 1 (mod p^2) for some A in the range 2 <= A <= p-1.
%C A134307 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.
%C A134307 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.
%C A134307 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
%C A134307 Replacing p^2 with p^3 gives just the one term (113) for p < 10^6. - _Joerg Arndt_, Jan 07 2011
%C A134307 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
%C A134307 The number of terms not exceeding prime(10^k), for k=1,2,..., are 2, 55, 652, 6303, 63219, ... - _Amiram Eldar_, May 08 2021
%D A134307 L. E. Dickson, History of the theory of numbers, vol. 1, p. 105.
%H A134307 Amiram Eldar, <a href="/A134307/b134307.txt">Table of n, a(n) for n = 1..10000</a> (terms 1..1000 from T. D. Noe)
%H A134307 Wilfrid Keller and Jörg Richstein <a href="https://web.archive.org/web/20140809030451/http://www1.uni-hamburg.de/RRZ/W.Keller/FermatQuotient.html">Fermat quotients that are divisible by p</a>.
%e A134307 Examples (pairs [p, A]):
%e A134307 [11, 3]
%e A134307 [11, 9]
%e A134307 [29, 14]
%e A134307 [37, 18]
%e A134307 [43, 19]
%e A134307 [59, 53]
%e A134307 [71, 11]
%e A134307 [71, 26]
%e A134307 [79, 31]
%e A134307 [97, 53]
%t A134307 Select[ Prime[ Range[100]], Product[ (PowerMod[a, # - 1, #^2] - 1), {a, 2, # - 1}] == 0 &] (* _Jonathan Sondow_, Feb 11 2013 *)
%o A134307 (PARI)
%o A134307 { forprime (p=2, 1000,
%o A134307    for (a=2, p-1, p2 = p^2;
%o A134307      if( Mod(a, p2)^(p-1) == Mod(1, p2), print1(p, ", ") ;break() );
%o A134307   ); ); }
%Y A134307 Cf. A001220, A055578, A039678, A143548, A222184, A060503.
%K A134307 nonn
%O A134307 1,1
%A A134307 _Joerg Arndt_, Aug 27 2008