Fermat quotient

In number theory, the Fermat quotient of an integer a with respect to an odd prime p is defined as

$q_p(a)=\frac{a^{p-1}-1}{p},$

or

${\delta }_p(a)=\frac{a-a^p}{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 q_p(a) will be an integer. If the base a is also a generator of the multiplicative group of integers modulo p, then q_p(a) will be a cyclic number, and p will be a full reptend prime.

Properties

From the definition, it is obvious that

$\begin{array}{cccc}{q}_p(1)& \equiv 0& & (\mathrm{mod}p)\\ q_p(-a)& \equiv q_p(a)& & (\mathrm{mod}p)(\text{since }2\mid p-1)\end{array}$

In 1850, Gotthold Eisenstein proved that if a and b are both coprime to p, then:

$\begin{array}{cccc}{q}_p(ab)& \equiv q_p(a)+q_p(b)& & (\mathrm{mod}p)\\ q_p(a^r)& \equiv r{q}_p(a)& & (\mathrm{mod}p)\\ q_p(p\mp a)& \equiv q_p(a)\pm \frac{1}{a}& & (\mathrm{mod}p)\\ q_p(p\mp 1)& \equiv \pm 1& & (\mathrm{mod}p)\end{array}$

Eisenstein likened the first two of these congruences to properties of logarithms. These properties imply

$\begin{array}{cccc}{q}_p\left(\frac{1}{a}\right)& \equiv -q_p(a)& & (\mathrm{mod}p)\\ q_p\left(\frac{a}{b}\right)& \equiv q_p(a)-q_p(b)& & (\mathrm{mod}p)\end{array}$

In 1895, Dmitry Mirimanoff pointed out that an iteration of Eisenstein's rules gives the corollary:

$q_p(a+np)\equiv q_p(a)-n\cdot \frac{1}{a}(\mathrm{mod}p).$

From this, it follows that:

$q_p(a+n{p}^2)\equiv q_p(a)(\mathrm{mod}p).$

Lerch's formula

M. Lerch proved in 1905 that

$\sum _{j=1}^{p-1}{q}_p(j)\equiv W_p(\mathrm{mod}p).$

Here $W_p$ 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}:

$-2q_p(2)\equiv \sum _{k=1}^{\frac{p-1}{2}}\frac{1}{k}(\mathrm{mod}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:

$-3q_p(2)\equiv \sum _{k=1}^{\lfloor \frac{p}{4}\rfloor }\frac{1}{k}(\mathrm{mod}p).$

$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}(\mathrm{mod}p).$

$2q_p(2)\equiv \sum _{k=\lfloor \frac{p}{6}\rfloor +1}^{\lfloor \frac{p}{3}\rfloor }\frac{1}{k}(\mathrm{mod}p).$

Eisenstein's series also has an increasingly complex connection to the Fermat quotients with other bases, the first few examples being:

$-3q_p(3)\equiv 2\sum _{k=1}^{\lfloor \frac{p}{3}\rfloor }\frac{1}{k}(\mathrm{mod}p).$

$-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}(\mathrm{mod}p).$

Generalized Wieferich primes

If q_p(a) ≡ 0 (mod p) then a^p−1 ≡ 1 (mod p²). 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 q_p(a) ≡ 0 (mod p) for small values of a are:

a	p (checked up to 5 × 1013)	OEIS sequence
1	2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ... (All primes)	Template:OEIS link
2	1093, 3511	Template:OEIS link
3	11, 1006003	Template:OEIS link
4	1093, 3511
5	2, 20771, 40487, 53471161, 1645333507, 6692367337, 188748146801	Template:OEIS link
6	66161, 534851, 3152573	Template:OEIS link
7	5, 491531	Template:OEIS link
8	3, 1093, 3511
9	2, 11, 1006003
10	3, 487, 56598313	Template:OEIS link
11	71
12	2693, 123653	Template:OEIS link
13	2, 863, 1747591	Template:OEIS link
14	29, 353, 7596952219	Template:OEIS link
15	29131, 119327070011	Template:OEIS link
16	1093, 3511
17	2, 3, 46021, 48947, 478225523351	Template:OEIS link
18	5, 7, 37, 331, 33923, 1284043	Template:OEIS link
19	3, 7, 13, 43, 137, 63061489	Template:OEIS link
20	281, 46457, 9377747, 122959073	Template:OEIS link
21	2
22	13, 673, 1595813, 492366587, 9809862296159	Template:OEIS link
23	13, 2481757, 13703077, 15546404183, 2549536629329	Template:OEIS link
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 and.

The smallest solutions of q_p(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, ... Template:OEIS

A pair (p, r) of prime numbers such that q_p(r) ≡ 0 (mod p) and q_r(p) ≡ 0 (mod r) is called a Wieferich pair.

External links

• Gottfried Helms. Fermat-/Euler-quotients (a^p-1 – 1)/p^k with arbitrary k.
• Richard Fischer. Fermat quotients B^(P-1) == 1 (mod P^2).