6
$\begingroup$

(I've taken this from MSE, it seems to be more appropriate here)

I'm rereading an older text on fermat-quotients (see wikipedia) from which I have now the

Question for $$ b^{p-1} \equiv 1 \pmod{ p^m} \qquad \text{ with $p \in \mathbb P $, $1 \lt b \lt p$ and $m \gt 2$} $$ (This is a generalization of the question for Wieferich primes).

Note that I ask here for examples, where the bases $b$ are smaller than the prime $p$, so a very well known weaker case $3^{10} \equiv 1 \pmod {11^2 } $ were an example, but only if the exponent at $11$ where one more; however frequent and well known cases like $18^6 \equiv 1 \pmod {7^3} $ were not because the base is bigger than the prime.

The only example that I've found so far is $$ 68^{112} \equiv 1 \pmod {113^3 } $$ but I've scanned only the first 2000 primes $p \in (3 \ldots 17389)$ and my primitive brute force algorithm has more than quadratic time-characteristic, so checking 10 000 or 100 000 primes were no fun - the quadratic regression prognoses 1 hour for testing 10 000 primes and 101 hours for testing 100 000 primes...

I'm aware of a couple of webpages containing lists of fermat quotients up to much higher primes, but either there is no explicite mention of the cases of $b \lt p$ and quotient $m \gt 2$ or I've been too dense when scanning through the listings (Richard Fischer, Wilfrid Keller, Michael Mossinghoff)


For reference: my Pari/GP-code is

for(j=2,2000,p=prime(j);p3=p^3;
    for(k=2,p-1,
        r = lift(Mod(k,p3)^(p-1));
        if(r==1,print(p," ",k," ",r)));
    );

(One correspondent took this up to the 10 000'th prime which is $p=104729$ )


[update] For the later casual reader I've included a more involved explanation and a table of data. See here (filesize 2Mb, inconvenient for modem-transfer)

$\endgroup$
  • 3
    $\begingroup$ Cases b<p can be easily identified in Fischer's table fermatquotient.com/FermatQuotienten/FermatQ3 and there no other for primes below 3.6*10^8. $\endgroup$ – Max Alekseyev Dec 7 '13 at 1:52
  • 2
    $\begingroup$ The question is discussed in MR2114655 (2005i:11004) Keller, Wilfrid; Richstein, Jörg; Solutions of the congruence $a^{p-1}\equiv1\pmod{p^r}$, Math. Comp. 74 (2005), no. 250, 927–936 but I don't think any solutions are found, other than the one you already have. Still, the paper might be worth a look, to see what's been done. $\endgroup$ – Gerry Myerson Dec 7 '13 at 4:34
  • $\begingroup$ Thanks to Max and Gerry for the links - I could access them both and also got the article of Keller/Richstein. $\endgroup$ – Gottfried Helms Dec 7 '13 at 5:16
  • $\begingroup$ @Max : if you would like to convert your comment into an answer I could mark that as accepted which would then "close the case"... $\endgroup$ – Gottfried Helms Dec 7 '13 at 15:39
6
$\begingroup$

Cases with $b<p$ can be easily identified in Fischer's table http://fermatquotient.com/FermatQuotienten/FermatQ3 and there are no other such instances for primes below $3.6\cdot 10^8$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.