Which primes $p$ divide $q^q-1$ for a prime divisor $q$ of $p-1$

I am looking for (a formula) for all the primes $p$ less than or equal to $X$ with the following criteria:

There is at least one prime $q$ dividing $p-1$ such that $p$ divides $q^q-1$.

$7$, for example is not one of these primes since $7$ does not divide $2^2-1$ or $3^3-1$. $11$ is a good example since $11$ divides $2^2-1$ or $5^5-1$.

What primes $p$ are these less than $1000$ for example. Thanks for helping.

• If $p-1$ has $n$ prime factors-$\{q_1\cdots q_n\}$, should $p$ divide $(q_i^{q_i}-1)\ \ \forall i\in\{1,\cdots,n\}$? – Qwerty Jul 23 '16 at 16:23
• First fix $q$ and consider a prime factor $p$ of $q^q-1$ that is greater than $p$. Then $q$ divides $p-1$. Eg: $q=3,p=13$. – Aravind Jul 23 '16 at 16:25
• @arctictern I think that OP means "at least one prime". Note that $p-1$ will be even, but $p$ will not divide $2^2-1$. (Except for $p=3$). – ajotatxe Jul 23 '16 at 16:31
• @ajotatxe That's what I said. – arctic tern Jul 23 '16 at 16:32
• For your search, you could also fix the factor $r=\dfrac{(p-1)}{q}$. For example, when $r=2$, you are looking at primes $q$ such that $2q+1$ is also prime and $q$ is 1 mod 4. Some examples are $q=5$, $q=29$, $q=41$ which give values of $p=11,59,83$. – Aravind Jul 23 '16 at 16:33

Just to provide more than a handful of data.
1) This is the code I used in Pari/GP :

  list=vectorv(1000);li=0;
{forprime(p=2,11333, \\  11333 is just a "idle-typing" value
f=factor(p-1);
for(k=1,rows(f),
q=f[k,1];
if((q^q-1) % p == 0 ,
li++;list[li]=[p,q,(p-1)/q ]
))
);}
list=Mat(VE(list,li))      \\ VE is a private short from for "vecextract"
listso = vecsort(list~,[3,1])~


2) This is the sorted data-table (note, that I didn't find one $p$ with two solutions $q$) :

      p     q   (p-1)/q
---------------------
3     2    1
11     5    2
59    29    2
83    41    2
107    53    2
179    89    2
227   113    2
347   173    2
467   233    2
563   281    2
587   293    2
1019   509    2
1187   593    2
1283   641    2
1307   653    2
1523   761    2
1619   809    2
1907   953    2
2027  1013    2
2099  1049    2
2459  1229    2
2579  1289    2
2819  1409    2
2963  1481    2
3203  1601    2
3467  1733    2
3779  1889    2
3803  1901    2
3947  1973    2
4139  2069    2
4259  2129    2
4283  2141    2
4547  2273    2
4787  2393    2
5099  2549    2
5387  2693    2
5483  2741    2
5507  2753    2
5939  2969    2
6659  3329    2
6779  3389    2
6827  3413    2
6899  3449    2
7187  3593    2
7523  3761    2
7643  3821    2
8147  4073    2
8699  4349    2
8747  4373    2
8819  4409    2
8963  4481    2
9467  4733    2
9587  4793    2
10163  5081    2
10667  5333    2
10883  5441    2
11003  5501    2
13     3    4
29     7    4
53    13    4
149    37    4
173    43    4
269    67    4
293    73    4
317    79    4
389    97    4
509   127    4
557   139    4
653   163    4
773   193    4
797   199    4
1109   277    4
1229   307    4
1493   373    4
1637   409    4
1733   433    4
1949   487    4
1997   499    4
2309   577    4
2477   619    4
2693   673    4
2837   709    4
2909   727    4
2957   739    4
3413   853    4
3533   883    4
3677   919    4
3989   997    4
4133  1033    4
4157  1039    4
4253  1063    4
4349  1087    4
4373  1093    4
4493  1123    4
4517  1129    4
5189  1297    4
5309  1327    4
5693  1423    4
5717  1429    4
5813  1453    4
6173  1543    4
6197  1549    4
6269  1567    4
6317  1579    4
6389  1597    4
6653  1663    4
7013  1753    4
7109  1777    4
7517  1879    4
7949  1987    4
8069  2017    4
8117  2029    4
8573  2143    4
9173  2293    4
9533  2383    4
9749  2437    4
10589  2647    4
10709  2677    4
10733  2683    4
10853  2713    4
11069  2767    4
11213  2803    4
439    73    6
607   101    6
1087   181    6
1399   233    6
1447   241    6
2239   373    6
2383   397    6
3343   557    6
3559   593    6
3607   601    6
3919   653    6
5119   853    6
6079  1013    6
7159  1193    6
8887  1481    6
9319  1553    6
9679  1613    6
11239  1873    6
1049   131    8
1097   137    8
1193   149    8
3833   479    8
4457   557    8
4937   617    8
6569   821    8
7577   947    8
7817   977    8
9209  1151    8
10457  1307    8
10889  1361    8
1931   193   10
3491   349   10
7331   733   10
10331  1033   10
709    59   12
1213   101   12
1237   103   12
2797   233   12
3373   281   12
5557   463   12
9277   773   12
11149   929   12
71     5   14
4943   353   14
977    61   16
2417   151   16
2609   163   16
2897   181   16
4337   271   16
5009   313   16
6737   421   16
8753   547   16
10289   643   16
10243   569   18
461    23   20
2617   109   24
8377   349   24
11117   397   28
3391   113   30
2657    83   32
1693    47   36
1999    37   54
1289    23   56
5657   101   56
4021    67   60
8363   113   74
7993    37  216
10949    17  644
4733     7  676

• These calculators are wonderful. I would like to learn to manage. – Piquito Jul 24 '16 at 13:03

There are $168$ primes $p\lt 1000$ and you want to pick among them all $p$ such that for at least one prime $q$ divisor of $p-1$ one has $p$ divides $q^q-1$. So you want to have in the field $\mathbb F_p$ the equality $$q^q=1$$ It is clear that one has to test just the factor primes $q$ of $p-1$ such that $q^q-1\ge p$, therefore when $p$ increases, one can rule out small prime factors $q$.

Waiting for a theoretical answer (which I find difficult indeed) I show here what I can do for the biggest three, $983,991$ and $997$ of the concerned primes before giving some final comments on your problem.

1) In the field $\mathbb F_{997}$

$996=2^2\cdot3\cdot83$ hence $2$ and $3$ are discarded and one has to calculate $$83^{83}=x$$ If $x=1$ then $(997,83)$ is one of the required examples and if $x\ne 1$ we discard the prime $p=997$. We have $$83^{83}=(83^{20})^4(83)^3=(16)^4\cdot 506=-1$$ hence one rule out the prime $997$.

2) In the field $\mathbb F_{991}$.

$990=2\cdot3^2\cdot5\cdot11$ so we need to solve $$5^5=x \text{ and } 11^{11}=x$$ $$\begin{cases}5^5=x\Rightarrow x=152\\11^{11}=x\Rightarrow x=766\end{cases}$$ hence one rule out the prime $991$.

3) In the field $\mathbb F_{983}$.

$982=2\cdot 491$ so we must solve $$491^{491}=x$$ Using the equalities $491^{10}=24$, $24^9=22$ and $24^{22}=25$ in $\mathbb F_{983}$, one has $$491^{491}=(24)^{49}\cdot 491=(24^{22})^2((24)^5\cdot 491=-1$$

hence one rules out the prime $983$. $$****$$ If no mistakes in calculation, none of the three considered primes must be saved. It remains $165$ primes to check where, for example, for $p=887$ you have the factor $q=443$ of $886$, for $p=863$ the factor $q=431$ and for $p=839$ the factor $q=419$ which leads to calculations not immediate to solve as for the already discarded prime $p = 983$.

A last remark is that if you would have asked for $q ^ q + 1$ instead of $q^q-1$, then the primes $997$ and $983$ have been taking in account. Where does it come your problem?

• I was studying this problem to check the divisors of $q^q-1$ and found that except for $q-1$ and $q$, all divisors $r$ of $q^q-1$ $=$ $1$ $\pmod q$. Then found that only a few primes $p$ divide $q^q-1$, with $q$ prime and most don't. With $q^q+1$, this would add more primes with the criterion above. All Sophie Germain Primes divide $q^q-1$ or $q^q+1$ for some prime $q$. – J. Linne Jul 24 '16 at 4:18
• The big problem, J. Linne, is there is not a criterium to find the factors of $p-1$ and when you take some larges $p$ it will appear, undoubtely, a big prime $q$ (dividing $p-1$) so you have to try with $q^q-1\equiv 0\pmod p$ which is, in each case, a distinct hard calculation question. The good news is that for many primes the corresponding factor $q$ can be small so discarded at first sight but the primes to be keep are absolutely unpredictable therefore "a formula" I see very out of reach. I wish I was wrong. Good luck. – Piquito Jul 24 '16 at 12:46