In number theory, the Fermat quotient of an integer a with respect to an odd prime p is defined as[1] [2] [3]
qp(a)=
| ap-1-1 | |
| p |
,
or
\deltap(a)=
| a-ap | |
| p |
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.
From the definition, it is obvious that
\begin{align} qp(1)&\equiv0&&\pmod{p}\\ qp(-a)&\equivqp(a)&&\pmod{p} (since2\midp-1) \end{align}
In 1850, Gotthold Eisenstein proved that if a and b are both coprime to p, then:[4]
\begin{align} qp(ab)&\equivqp(a)+qp(b)&&\pmod{p}
| r) | |
| \\ q | |
| p(a |
&\equivrqp(a)&&\pmod{p}\\ qp(p\mpa)&\equivqp(a)\pm\tfrac{1}{a}&&\pmod{p}\\ qp(p\mp1)&\equiv\pm1&&\pmod{p} \end{align}
Eisenstein likened the first two of these congruences to properties of logarithms. These properties imply
\begin{align} qp\left(\tfrac{1}{a}\right)&\equiv-qp(a)&&\pmod{p}\\ qp\left(\tfrac{a}{b}\right)&\equivqp(a)-qp(b)&&\pmod{p} \end{align}
In 1895, Dmitry Mirimanoff pointed out that an iteration of Eisenstein's rules gives the corollary:[5]
qp(a+np)\equivqp(a)-n ⋅ \tfrac{1}{a}\pmod{p}.
From this, it follows that:[6]
| 2)\equiv | |
| q | |
| p(a+np |
qp(a)\pmod{p}.
M. Lerch proved in 1905 that[7] [8] [9]
| p-1 | |
| \sum | |
| j=1 |
qp(j)\equivWp\pmod{p}.
Here
Wp
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 :
-2qp(2)\equiv
| ||||
| \sum | ||||
| k=1 |
| 1 | |
| k |
\pmod{p}.
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:
-3qp(2)\equiv
| |||||
| \sum | |||||
| k=1 |
| 1 | |
| k |
\pmod{p}.
4qp(2)\equiv
| |||||
| \sum | |||||
|
| 1 | |
| k |
+
| |||||
| \sum | |||||
|
| 1 | |
| k |
\pmod{p}.
2qp(2)\equiv
| |||||
| \sum | |||||
|
| 1 | |
| k |
\pmod{p}.
Eisenstein's series also has an increasingly complex connection to the Fermat quotients with other bases, the first few examples being:
-3qp(3)\equiv
| |||||
| 2\sum | |||||
| k=1 |
| 1 | |
| k |
\pmod{p}.
-5qp(5)\equiv
| |||||
| 4\sum | |||||
| k=1 |
| 1 | |
| k |
+
| |||||
| 2\sum | |||||
|
| 1 | |
| k |
\pmod{p}.
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:[1]
| a | p (checked up to 5 × 1013) | OEIS sequence | |
|---|---|---|---|
| 1 | 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ... (All primes) | ||
| 2 | 1093, 3511 | ||
| 3 | 11, 1006003 | ||
| 4 | 1093, 3511 | ||
| 5 | 2, 20771, 40487, 53471161, 1645333507, 6692367337, 188748146801 | ||
| 6 | 66161, 534851, 3152573 | ||
| 7 | 5, 491531 | ||
| 8 | 3, 1093, 3511 | ||
| 9 | 2, 11, 1006003 | ||
| 10 | 3, 487, 56598313 | ||
| 11 | 71 | ||
| 12 | 2693, 123653 | ||
| 13 | 2, 863, 1747591 | ||
| 14 | 29, 353, 7596952219 | ||
| 15 | 29131, 119327070011 | ||
| 16 | 1093, 3511 | ||
| 17 | 2, 3, 46021, 48947, 478225523351 | ||
| 18 | 5, 7, 37, 331, 33923, 1284043 | ||
| 19 | 3, 7, 13, 43, 137, 63061489 | ||
| 20 | 281, 46457, 9377747, 122959073 | ||
| 21 | 2 | ||
| 22 | 13, 673, 1595813, 492366587, 9809862296159 | ||
| 23 | 13, 2481757, 13703077, 15546404183, 2549536629329 | ||
| 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 [16] [17] [18] and.[19]
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, ...
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.
| ap-1-1 | |
| p |
=q(a)
1n+2n+ … +kn=(k+1)n
k
k2