# 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:18:01 CEST 2008

```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.

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.
>
>

```