Primes p such that x = order(x) modulo p

[Max A.]

On 1/8/07, Nick Hobson <nickh at qbyte.org> wrote:

> The following primes are such that for at least one x in 2...p-1, the
> order of x modulo p is equal to x.  For example, the order of 3 modulo 13
> is 3, since 3^3 = 1 (mod 13), while 3^2 and 3^1 != 1 (mod 13).
>
> 3, 11, 13, 17, 19, 29, 31, 37, 41, 53, 59, 61, 67, 71, 73, 83, 89, 97
>
> PARI script: forprime(p=3, 97, for(x=2, p-1, if(znorder(Mod(x, p))==x,
> print1(p, ", "); break)))
>
> Is this of general interest?

Another characterization of this sequence:

Let P(n) be a set of primitive prime divisors of n^n - 1 in the
sequence {n^1 - 1, n^2 - 1, ...}.
Then your sequence gives the union of P(n), n=2,3,..oo, in the increasing order.

It is interesting to notice that according to Zsigmondy Theorem
http://mathworld.wolfram.com/ZsigmondyTheorem.html
P(n) is not empty for any n>1. In other words, every x=2,3,... serve
as a proof for at least one prime to belong to your sequence.

For n=2..10, the set P(n) equals:
n=2: [3]
n=3: [13]
n=4: [17]
n=5: [11, 71]
n=6: [31]
n=7: [29, 4733]
n=8: [17, 241]
n=9: [19, 37, 757]
n=10: [9091]

Max