Fermat quotient
In number theory, the Fermat quotient of an integer a with respect to an odd prime p is defined as[1][2][3][4]
- [math]\displaystyle{ q_p(a) = \frac{a^{p-1}-1}{p}, }[/math]
or
- [math]\displaystyle{ \delta_p(a) = \frac{a - a^p }{p} }[/math].
This article is about the former; for the latter see p-derivation. The quotient is named after Pierre de Fermat.
If the base a is coprime to the exponent p then Fermat's little theorem says that qp(a) will be an integer. If the base a is also a generator of the multiplicative group of integers modulo p, then qp(a) will be a cyclic number, and p will be a full reptend prime.
Properties
From the definition, it is obvious that
- [math]\displaystyle{ \begin{align} q_p(1) &\equiv 0 && \pmod{p} \\ q_p(-a)&\equiv q_p(a) && \pmod{p}\quad (\text{since } 2 \mid p-1) \end{align} }[/math]
In 1850, Gotthold Eisenstein proved that if a and b are both coprime to p, then:[5]
- [math]\displaystyle{ \begin{align} q_p(ab) &\equiv q_p(a)+q_p(b) &&\pmod{p} \\ q_p(a^r) &\equiv rq_p(a) &&\pmod{p} \\ q_p(p \mp a) &\equiv q_p(a) \pm \tfrac{1}{a} &&\pmod{p} \\ q_p(p \mp 1) &\equiv \pm 1 && \pmod{p} \end{align} }[/math]
Eisenstein likened the first two of these congruences to properties of logarithms. These properties imply
- [math]\displaystyle{ \begin{align} q_p \!\left(\tfrac{1}{a} \right) &\equiv -q_p(a) && \pmod{p} \\ q_p \!\left(\tfrac{a}{b} \right) &\equiv q_p(a) - q_p(b) &&\pmod{p} \end{align} }[/math]
In 1895, Dmitry Mirimanoff pointed out that an iteration of Eisenstein's rules gives the corollary:[6]
- [math]\displaystyle{ q_p(a+np)\equiv q_p(a)-n\cdot\tfrac{1}{a} \pmod{p}. }[/math]
From this, it follows that:[7]
- [math]\displaystyle{ q_p(a+np^2)\equiv q_p(a) \pmod{p}. }[/math]
Lerch's formula
M. Lerch proved in 1905 that[8][9][10]
- [math]\displaystyle{ \sum_{j=1}^{p-1}q_p(j)\equiv W_p\pmod{p}. }[/math]
Here [math]\displaystyle{ W_p }[/math] is the Wilson quotient.
Special values
Eisenstein discovered that the Fermat quotient with base 2 could be expressed in terms of the sum of the reciprocals modulo p of the numbers lying in the first half of the range {1, ..., p − 1}:
- [math]\displaystyle{ -2q_p(2) \equiv \sum_{k=1}^{\frac{p-1}{2}} \frac{1}{k} \pmod{p}. }[/math]
Later writers showed that the number of terms required in such a representation could be reduced from 1/2 to 1/4, 1/5, or even 1/6:
- [math]\displaystyle{ -3q_p(2) \equiv \sum_{k=1}^{\lfloor\frac{p}{4}\rfloor} \frac{1}{k} \pmod{p}. }[/math][11]
- [math]\displaystyle{ 4q_p(2) \equiv \sum_{k=\lfloor\frac{p}{10}\rfloor + 1}^{\lfloor\frac{2p}{10}\rfloor} \frac{1}{k} + \sum_{k=\lfloor\frac{3p}{10}\rfloor + 1}^{\lfloor\frac{4p}{10}\rfloor} \frac{1}{k} \pmod{p}. }[/math][12]
- [math]\displaystyle{ 2q_p(2) \equiv \sum_{k=\lfloor\frac{p}{6}\rfloor+1}^{\lfloor\frac{p}{3}\rfloor} \frac{1}{k} \pmod{p}. }[/math][13][14]
Eisenstein's series also has an increasingly complex connection to the Fermat quotients with other bases, the first few examples being:
- [math]\displaystyle{ -3q_p(3) \equiv 2\sum_{k=1}^{\lfloor\frac{p}{3}\rfloor} \frac{1}{k} \pmod{p}. }[/math][15]
- [math]\displaystyle{ -5q_p(5) \equiv 4\sum_{k=1}^{\lfloor\frac{p}{5}\rfloor} \frac{1}{k} + 2\sum_{k=\lfloor\frac{p}{5}\rfloor+1}^{\lfloor\frac{2p}{5}\rfloor} \frac{1}{k} \pmod{p}. }[/math][16]
Generalized Wieferich primes
If qp(a) ≡ 0 (mod p) then ap−1 ≡ 1 (mod p2). Primes for which this is true for a = 2 are called Wieferich primes. In general they are called Wieferich primes base a. Known solutions of qp(a) ≡ 0 (mod p) for small values of a are:[2]
a p (checked up to 5 × 1013) OEIS sequence 1 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ... (All primes) A000040 2 1093, 3511 A001220 3 11, 1006003 A014127 4 1093, 3511 5 2, 20771, 40487, 53471161, 1645333507, 6692367337, 188748146801 A123692 6 66161, 534851, 3152573 A212583 7 5, 491531 A123693 8 3, 1093, 3511 9 2, 11, 1006003 10 3, 487, 56598313 A045616 11 71 12 2693, 123653 A111027 13 2, 863, 1747591 A128667 14 29, 353, 7596952219 A234810 15 29131, 119327070011 A242741 16 1093, 3511 17 2, 3, 46021, 48947, 478225523351 A128668 18 5, 7, 37, 331, 33923, 1284043 A244260 19 3, 7, 13, 43, 137, 63061489 A090968 20 281, 46457, 9377747, 122959073 A242982 21 2 22 13, 673, 1595813, 492366587, 9809862296159 A298951 23 13, 2481757, 13703077, 15546404183, 2549536629329 A128669 24 5, 25633 25 2, 20771, 40487, 53471161, 1645333507, 6692367337, 188748146801 26 3, 5, 71, 486999673, 6695256707 27 11, 1006003 28 3, 19, 23 29 2 30 7, 160541, 94727075783
For more information, see [17][18][19] and.[20]
The smallest solutions of qp(a) ≡ 0 (mod p) with a = n are:
- 2, 1093, 11, 1093, 2, 66161, 5, 3, 2, 3, 71, 2693, 2, 29, 29131, 1093, 2, 5, 3, 281, 2, 13, 13, 5, 2, 3, 11, 3, 2, 7, 7, 5, 2, 46145917691, 3, 66161, 2, 17, 8039, 11, 2, 23, 5, 3, 2, 3, ... (sequence A039951 in the OEIS)
A pair (p, r) of prime numbers such that qp(r) ≡ 0 (mod p) and qr(p) ≡ 0 (mod r) is called a Wieferich pair.
References
- ↑ Weisstein, Eric W.. "Fermat Quotient". http://mathworld.wolfram.com/FermatQuotient.html.
- ↑ 2.0 2.1 Fermat Quotient at The Prime Glossary
- ↑ Paulo Ribenboim, 13 Lectures on Fermat's Last Theorem (1979), especially pp. 152, 159-161.
- ↑ Paulo Ribenboim, My Numbers, My Friends: Popular Lectures on Number Theory (2000), p. 216.
- ↑ Gotthold Eisenstein, "Neue Gattung zahlentheoret. Funktionen, die v. 2 Elementen abhangen und durch gewisse lineare Funktional-Gleichungen definirt werden," Bericht über die zur Bekanntmachung geeigneten Verhandlungen der Königl. Preuß. Akademie der Wissenschaften zu Berlin 1850, 36-42
- ↑ Dmitry Mirimanoff, "Sur la congruence (rp − 1 − 1):p = qr (mod p)," Journal für die reine und angewandte Mathematik 115 (1895): 295-300
- ↑ Paul Bachmann, Niedere Zahlentheorie, 2 vols. (Leipzig, 1902), 1:159.
- ↑ Lerch, Mathias (1905). "Zur Theorie des Fermatschen Quotienten [math]\displaystyle{ \frac{a^{p-1}-1}{p}=q(a) }[/math]". Mathematische Annalen 60: 471–490. doi:10.1007/bf01561092.
- ↑ Sondow, Jonathan (2014). "Lerch quotients, Lerch primes, Fermat-Wilson quotients, and the Wieferich-non-Wilson primes 2, 3, 14771". arXiv:1110.3113 [math.NT].
- ↑ Sondow, Jonathan; MacMillan, Kieren (2011). "Reducing the Erdős-Moser equation [math]\displaystyle{ 1^n+2^n+\cdots+k^n=(k+1)^n }[/math] modulo [math]\displaystyle{ k }[/math] and [math]\displaystyle{ k^2 }[/math]". arXiv:1011.2154 [math.NT].
- ↑ James Whitbread Lee Glaisher, "On the Residues of rp − 1 to Modulus p2, p3, etc.," Quarterly Journal of Pure and Applied Mathematics 32 (1901): 1-27.
- ↑ Ladislav Skula, "A note on some relations among special sums of reciprocals modulo p," Mathematica Slovaca 58 (2008): 5-10.
- ↑ Emma Lehmer, "On Congruences involving Bernoulli Numbers and the Quotients of Fermat and Wilson," Annals of Mathematics 39 (1938): 350–360, pp. 356ff.
- ↑ Karl Dilcher and Ladislav Skula, "A New Criterion for the First Case of Fermat's Last Theorem," Mathematics of Computation 64 (1995): 363-392.
- ↑ James Whitbread Lee Glaisher, "A General Congruence Theorem relating to the Bernoullian Function," Proceedings of the London Mathematical Society 33 (1900-1901): 27-56, at pp. 49-50.
- ↑ Mathias Lerch, "Zur Theorie des Fermatschen Quotienten…," Mathematische Annalen 60 (1905): 471-490.
- ↑ Wieferich primes to bases up to 1052
- ↑ Wieferich.txt primes to bases up to 10125
- ↑ Wieferich prime in prime bases up to 1000
- ↑ Wieferich primes with level >= 3
External links
- Gottfried Helms. Fermat-/Euler-quotients (ap-1 – 1)/pk with arbitrary k.
- Richard Fischer. Fermat quotients B^(P-1) == 1 (mod P^2).
![]() | Original source: https://en.wikipedia.org/wiki/Fermat quotient.
Read more |