Available in electronic format
Available in print format
Mathematics of Computation
Journal of the American Mathematical Society
ISSN 1088-6842(e) ISSN 0025-5718(p)
     

Solutions of the congruence $a^{p-1} \equiv 1 \pmod {p^r}$

Author(s): Wilfrid Keller; Jörg Richstein.
Journal: Math. Comp. 74 (2005), 927-936.
MSC (2000): Primary 11A07; Secondary 11D61, 11--04
Posted: June 8, 2004
Retrieve article in: PDF DVI PostScript

Abstract | References | Similar articles | Additional information

Abstract: To supplement existing data, solutions of $a^{p-1} \equiv 1 \pmod {p^2}$ are tabulated for primes $a, p$with $100 < a < 1000$ and $10^4 < p < 10^{11}$. For $a < 100$, five new solutions $p > 2^{32}$ are presented. One of these, $p = 188748146801$ for $a = 5$, also satisfies the ``reverse'' congruence $p^{a-1} \equiv 1 \pmod {a^2}$. An effective procedure for searching for such ``double solutions'' is described and applied to the range $a < 10^6$, $p <\max\, (10^{11}, a^2)$. Previous to this, congruences $a^{p-1} \equiv 1 \pmod {p^r}$ are generally considered for any $r \ge 2$ and fixed prime $p$ to see where the smallest prime solution $a$ occurs.


References:

1.
M. Aaltonen and K. Inkeri, Catalan's equation $x^p - y^q = 1$ and related congruences, Math. Comp. 56 (1991), 359-370. MR 91g:11025

2.
N. G. W. H. Beeger, Quelques remarques sur les congruences $r^{p-1} \equiv 1 \pmod{p^2}$ et $(p-1)! \equiv -1 \pmod{p^2}$, Messenger of Math. 43 (1914), 72-84.

3.
D. Bressoud and S. Wagon, A course in computational number theory, Key College Publishing, Emeryville, CA, 2000. MR 2001f:11200

4.
J. Brillhart, J. Tonascia, and P. Weinberger, On the Fermat quotient, Computers in Number Theory (A. O. L. Atkin and B. J. Birch, eds.), Academic Press, London and New York, 1971, 213-222. MR 47:3288

5.
R. Brown, electronic mail dated 13 June 2001.

6.
R. Crandall, K. Dilcher, and C. Pomerance, A search for Wieferich and Wilson primes, Math. Comp. 66 (1997), 433-449. MR 97c:11004

7.
A. Cunningham, Period-lengths of circulates, Messenger of Math. 29 (1900), 145-179.

8.
R. Ernvall and T. Metsänkylä, On the $p$-divisibility of Fermat quotients, Math. Comp. 66 (1997), 1353-1365. http://users.utu.fi/taumets/fermat/fermat.htm. MR 97i:11003

9.
Y. Gallot, Proth.exe: A Windows program for finding very large primes, http://www.utm.edu /research/primes/programs/gallot/.

10.
K. Inkeri, On Catalan's conjecture, J. Number Theory 34 (1990), 142-152. MR 91e:11030

11.
W. Keller, New prime solutions $p$ of $a^{p-1} \equiv 1 \pmod{p^2}$, Abstracts Amer. Math. Soc. 9 (1988), 503.

12.
W. Keller and J. Richstein, Fermat quotients $q_p(a)$ that are divisible by $p$, http://www. informatik.uni-giessen.de/cnth/FermatQuotient.html.

13.
J. Knauer and J. Richstein, The continuing search for Wieferich primes, Math. Comp., to appear.

14.
R. McIntosh, electronic mail dated 23 February 2001.

15.
W. Meissner, Über die Lösungen der Kongruenz $x^{p-1} \equiv 1 \bmod {p^m}$ und ihre Verwertung zur Periodenbestimmung mod $p^\kappa$, Sitzungsber. Berliner Math. Ges. 13 (1914), 96-107.

16.
W. F. Meyer, Ergänzungen zum Fermatschen und Wilsonschen Satze, Arch. Math. Physik (3) 2 (1902), 141-146.

17.
M. Mignotte and Y. Roy, L'équation de Catalan, Prépubl. de l'IRMA 513/P-299, Université Louis Pasteur et CNRS, Strasbourg, 1992.

18.
P. L. Montgomery, New solutions of $a^{p-1} \equiv 1 \pmod{p^2}$, Math. Comp. 61 (1993), 361-363. MR 94d:11003

19.
P. Ribenboim, The new book of prime number records, 3rd ed., Springer-Verlag, New York, 1996. MR 96k:11112

20.
H. Riesel, Note on the congruence $a^{p-1} \equiv 1 \pmod{p^2}$, Math. Comp. 18 (1964), 149-150. MR 28:1156

21.
Worms de Romilly, Équation $a^{p-1} = 1\, +\, $mult. $p^2$, L'Intermédiaire des Math. 8 (1901), 214-215.


Similar Articles:

Retrieve articles in Mathematics of Computation with MSC (2000): 11A07, 11D61, 11--04

Retrieve articles in all Journals with MSC (2000): 11A07, 11D61, 11--04


Additional Information:

Wilfrid Keller
Affiliation: Universität Hamburg, 20146 Hamburg, Germany
Email: keller@rrz.uni-hamburg.de

Jörg Richstein
Affiliation: Department of Mathematics and Statistics, Dalhousie University, Halifax, Nova Scotia B3H 3J5, Canada
Email: joerg@mathstat.dal.ca

DOI: 10.1090/S0025-5718-04-01666-7
PII: S 0025-5718(04)01666-7
Keywords: Fermat quotient, Diophantine equation, primitive roots, large primes
Received by editor(s): July 30, 2001
Received by editor(s) in revised form: September 1, 2003.
Posted: June 8, 2004
Additional Notes: The second author was supported by the Killam Trusts.
Copyright of article: Copyright 2004, American Mathematical Society


  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2008, American Mathematical Society
Privacy Statement
Search the AMSPowered by Google