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]

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

or

δ_{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{matrix} q_{p} (1) & \equiv 0 & (\mod p) \\ q_{p} (- a) & \equiv q_{p} (a) & (\mod p) (since 2 ∣ p - 1) \end{matrix}

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

\begin{matrix} q_{p} (a b) & \equiv q_{p} (a) + q_{p} (b) & (\mod p) \\ q_{p} (a^{r}) & \equiv r q_{p} (a) & (\mod p) \\ q_{p} (p \mp a) & \equiv q_{p} (a) \pm \frac{1}{a} & (\mod p) \\ q_{p} (p \mp 1) & \equiv \pm 1 & (\mod p) \end{matrix}

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

\begin{matrix} q_{p} (\frac{1}{a}) & \equiv - q_{p} (a) & (\mod p) \\ q_{p} (\frac{a}{b}) & \equiv q_{p} (a) - q_{p} (b) & (\mod p) \end{matrix}

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

q_{p} (a + n p) \equiv q_{p} (a) - n \cdot \frac{1}{a} (\mod p) .

From this, it follows that:^[7]

q_{p} (a + n p^{2}) \equiv q_{p} (a) (\mod p) .

Lerch's formula

M. Lerch proved in 1905 that^[8]^[9]^[10]

\sum_{j = 1}^{p - 1} q_{p} (j) \equiv W_{p} (\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}:

- 2 q_{p} (2) \equiv \sum_{k = 1}^{\frac{p - 1}{2}} \frac{1}{k} (\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:

- 3 q_{p} (2) \equiv \sum_{k = 1}^{⌊ \frac{p}{4} ⌋} \frac{1}{k} (\mod p) .

^[11]

4 q_{p} (2) \equiv \sum_{k = ⌊ \frac{p}{10} ⌋ + 1}^{⌊ \frac{2 p}{10} ⌋} \frac{1}{k} + \sum_{k = ⌊ \frac{3 p}{10} ⌋ + 1}^{⌊ \frac{4 p}{10} ⌋} \frac{1}{k} (\mod p) .

^[12]

2 q_{p} (2) \equiv \sum_{k = ⌊ \frac{p}{6} ⌋ + 1}^{⌊ \frac{p}{3} ⌋} \frac{1}{k} (\mod p) .

^[13]^[14]

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

- 3 q_{p} (3) \equiv 2 \sum_{k = 1}^{⌊ \frac{p}{3} ⌋} \frac{1}{k} (\mod p) .

^[15]

- 5 q_{p} (5) \equiv 4 \sum_{k = 1}^{⌊ \frac{p}{5} ⌋} \frac{1}{k} + 2 \sum_{k = ⌊ \frac{p}{5} ⌋ + 1}^{⌊ \frac{2 p}{5} ⌋} \frac{1}{k} (\mod p) .

^[16]

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:^[2]

a	p (checked up to 5 × 10¹³)	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 ^[17]^[18]^[19] and.^[20]

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.

References

↑ Template:MathWorld
↑ ^2.0 ^2.1 Template:Cite web
↑ 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 (r^{p − 1} − 1):p = q_r (mod p)," Journal für die reine und angewandte Mathematik 115 (1895): 295-300
↑ Paul Bachmann, Niedere Zahlentheorie, 2 vols. (Leipzig, 1902), 1:159.
↑ Template:Cite journal
↑ Template:Cite arXiv
↑ Template:Cite arXiv
↑ James Whitbread Lee Glaisher, "On the Residues of r^{p − 1} to Modulus p², p³, 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
↑ Template:Cite web
↑ Wieferich prime in prime bases up to 1000 Template:Webarchive
↑ Wieferich primes with level >= 3

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).

[1] Template:MathWorld

[pg-2] 2.0 ^2.1 Template:Cite web

[3] Paulo Ribenboim, 13 Lectures on Fermat's Last Theorem (1979), especially pp. 152, 159-161.

[4] Paulo Ribenboim, My Numbers, My Friends: Popular Lectures on Number Theory (2000), p. 216.

[5] 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

[6] Dmitry Mirimanoff, "Sur la congruence (r^{p − 1} − 1):p = q_r (mod p)," Journal für die reine und angewandte Mathematik 115 (1895): 295-300

[7] Paul Bachmann, Niedere Zahlentheorie, 2 vols. (Leipzig, 1902), 1:159.

[Lerch-8] Template:Cite journal

[Sondow-9] Template:Cite arXiv

[SondowMacMillan-10] Template:Cite arXiv

[11] James Whitbread Lee Glaisher, "On the Residues of r^{p − 1} to Modulus p², p³, etc.," Quarterly Journal of Pure and Applied Mathematics 32 (1901): 1-27.

[12] Ladislav Skula, "A note on some relations among special sums of reciprocals modulo p," Mathematica Slovaca 58 (2008): 5-10.

[13] Emma Lehmer, "On Congruences involving Bernoulli Numbers and the Quotients of Fermat and Wilson," Annals of Mathematics 39 (1938): 350–360, pp. 356ff.

[14] Karl Dilcher and Ladislav Skula, "A New Criterion for the First Case of Fermat's Last Theorem," Mathematics of Computation 64 (1995): 363-392.

[15] 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.

[16] Mathias Lerch, "Zur Theorie des Fermatschen Quotienten…," Mathematische Annalen 60 (1905): 471-490.

[17] Wieferich primes to bases up to 1052

[18] Template:Cite web

[19] Wieferich prime in prime bases up to 1000 Template:Webarchive

[20] Wieferich primes with level >= 3

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

Fermat quotient

Contents

Properties

Lerch's formula

Special values

Generalized Wieferich primes

References

External links

Navigation menu

Fermat quotient

Properties

Lerch's formula

Special values

Generalized Wieferich primes

References

External links

Navigation menu

Search