Let S(A) be {1,2,3,...,(A-1)} and S'(A,B) be the set of elements X from S(A) that satisfy X^B mod A=1. Assuming that A is prime, find the sum of all the elements of S'(A,B) in terms of A and B.

Each value of A below is followed by the number of primes p < 10^8, with p=1 mod A, and such that S(p,A)/p = {1,2,3,...}:

A=5: {239638,960761,239899},
A=7: {8232,207702,528640,207451,7998},
A=9: {0,0,240910,479509,239540},
A=11: {3,785,23324,139765,247438,140686,23289,813},
A=13: {2,29,1833,26186,117314,189633,117004,26331,1776,24},
A=15: {0,0,0,0,45865,176038,276223,175990,45868},
A=17: {1,0,5,232,4055,28424,85445,123585,85666,28211,4028,215},
A=19: {1,0,0,18,421,5211,27869,75031,103154,74586,27915,5204,404,11},
A=21: {0,0,0,0,0,0,7535,45410,111972,150734,111787,45201,7412},
A=23: {0,0,0,0,4,61,928,6719,26504,58512,76509,58737,26267,6662,907,64,3},
A=25: {0,0,0,0,1,12,147,1412,8574,29945,63361,80565,63479,30285,8590,1444,145,4,1},

For example, S(p,5)/p = 1,2,3 in a ratio of 1:4:1, and S(p,9)/p = 3,4,5 in a 1:2:1 ratio.  For larger A, S(p,A)/p is roughly normal, with mean (A-1)/2, and variance ~ A/12.

If p=(x^A-1)/(x-1) is prime for some integer x, then S(p,A)=p.  It is likely that for any prime A, there are infinitely many such p, but there is no known proof.

I had thought maybe all solutions of S(p,A)=p with A>7 might be of this form, but that is not so.  For example, S(p,11)=p when p=315475 or p=84662887, but neither is of the form (x^11-1)/(x-1).

Anyway, I highly doubt a closed form for S(p,A) is possible; probably the best we can hope for is the density of primes with S(p,A)/p = k for each A,k.

Posted by Eigenray on 2007-08-31 23:56:30