# primes p s.t. there is an A s.t. A^(p-1)==1 mod p^2

Max Alekseyev maxale at gmail.com
Tue Aug 26 06:50:33 CEST 2008

```On Mon, Aug 25, 2008 at 9:18 PM, Max Alekseyev <maxale at gmail.com> wrote:
> If I got you correctly, you require that 1 < A < p.
> In other words, a prime p is in your sequence if there is an element
> of order p-1 modulo p^2 among 2,3,...,p-1.

Correction: here and below "order p-1" should be read as "order dividing p-1".

> It's worth to notice that there are p-1 elements of order 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 the
> probability about 1 - (1 - 1/p)^(p-1) ~= 1 - 1/e.
> Numerically, among primes below 1000 (of the total number
> pi(1000)=168) there 103 terms of your sequence, and the ratio 103/168
> ~= 0.613 which is already somewhat close to 1-1/e ~= 0.632.
>
> As of replacing p^2 with p^3, heuristically it likely that the
> sequence is finite (since 1 - (1 - 1/p^2)^(p-1) tends to 0 as p
> grows).
>
> Regards,
> Max
>
> On Mon, Aug 25, 2008 at 6:58 PM, Joerg Arndt <arndt at jjj.de> wrote:
>> seq. not in OEIS:
>>
>> 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, 521, 523, 547, 557,
>> 563, 571, 577, 599, 601, 607, 617, 619, 631, 641, 647, 653, 659, 661,
>> 673, 701, 727, 739, 743, 761, 769, 773, 797, 809, 823, 827, 829, 839,
>> 857, 859, 863, 877, 883, 887, 907, 911, 919, 941, 947, 953, 967, 971,
>> 977, 983, 991, 997,
>>
>> Examples (pairs [p, a]):
>> [11, 3]
>> [11, 9]
>> [29, 14]
>> [37, 18]
>> [43, 19]
>> [59, 53]
>> [71, 11]
>> [71, 26]
>> [79, 31]
>> [97, 53]
>>
>>
>>
>> { forprime (p=2,1000,
>>    for (a=2,p-1,
>>        p2 = p^2;
>>        q = ( Mod(a,p2)^(p-1) == Mod(1,p2) );
>>        if ( q , print1(p,",");break() );
>>    );
>>  ); }
>>
>> submit?
>> also submit complement?
>>
>> btw. 113 is the only prime with A^(p-1)==1 mod p^3 I could
>> find;  none for modulus p^k where k>3 so far.
>>
>>
>

```