The Fermat Quotient as a Dilation-Correlation Defect

A correlation defect that is exactly the Fermat quotient

The multiplicative dilation correlation of the block-harmonic sequence has defect exactly minus c times the Fermat quotient of 2, which recovers that quotient exactly.

Number theory Fermat quotients Sequences and correlation

R002 · New formulation of a classical identity

Informally proven · First published 2026-09-12

The construction

Fix a prime \(r > 3\), an integer \(c \ge 1\), and put

\[P = 2cr - 1, \qquad M = \frac{P-1}{2} = cr - 1, \qquad h = \frac{r-1}{2}.\]

When \(P\) is prime, the group \(G = (\mathbb{Z}/P\mathbb{Z})^\times / \{\pm 1\}\) has order \(M\), and each class has a unique representative \(\rho(x) \in \{1, \dots, M\}\) — the window.

Work in \(\mathbb{F}_r\), and let

\[H_0 = 0, \qquad H_j = 1 + \tfrac12 + \dots + \tfrac1j \in \mathbb{F}_r \quad (1 \le j \le r-1)\]

be the harmonic staircase, so in particular \(H_{r-1} = 0\). Define the block-harmonic sequence

\[F(x) = H_{\lfloor \rho(x)/(2c) \rfloor} \in \mathbb{F}_r,\]

and its dilation correlation at multiplicative lag \(a \in G\):

\[R(a) = \sum_{x \in G} F(x)\,F(ax) \in \mathbb{F}_r.\]

Finally let \(q_r(2) = (2^{r-1}-1)/r \bmod r\) be the Fermat quotient of \(2\) at \(r\), so that \(r\) is a base-2 Wieferich prime exactly when \(q_r(2) = 0\).

The sequence \(F\) is a staircase that rises by one step every \(2c\) units of the window; the doubling map \(x \mapsto 2x\) lands on exactly two half-blocks, and that is the entire reason the identity below has no error term.

NoteProvenance and status

Be warned about the novelty, because it is easy to overstate. The arithmetic content is classical. Given the combinatorial collapse of Lemma 2, Theorem 1 below is equivalent to Eisenstein’s 1850 congruence \(H_{(r-1)/2} \equiv -2q_r(2) \pmod r\); and Lerch (1905) already exhibited Fermat quotients as linear functionals of block harmonic sums, of which our \(F\) is exactly the shape. No new value of any \(q_r(a)\) is produced, and there is no algorithmic gain. What is new, as far as an extensive search reached, is the identification of that classical functional with the defect of an explicit multiplicative dilation correlation at the doubling lag, the error-term-free collapse, the exact-recovery form, and the uniqueness statement.

Terminology. The phrase “arithmetic correlation” already denotes the with-carry notion of Mandelbaum–Goresky–Klapper (IEEE Trans. Inform. Theory 58 (2012) 479–492). Ours is a multiplicative dilation correlation and is not an instance of theirs.

Elementary identities

Lemma 0. In \(\mathbb{F}_r\), extending \(H\) to indices \(h < i \le r-1\) by \(H_i := H_{r-1-i}\):

  1. Reflection: \(H_{r-1-i} = H_i\) for \(0 \le i \le r-1\).
  2. \(H_{r-1} = 0\), \(H_{r-2} = H_1 = 1\), \(H_{2h-2} = H_2 = 3/2\).
  3. \(1/h = -2\), hence \(H_{h-1} = H_h + 2\).
  4. Alternating: \(\sum_{k=1}^{2n}(-1)^{k-1}H_k = -H_n/2\) for \(0 \le n \le h\).
  5. \(\sum_{i=1}^{n}H_i = (n+1)H_n - n\) for \(0 \le n \le r-1\).

Proof.

  1. \(H_{r-1} = \sum_{k=1}^{r-1}1/k = \sum_{k=1}^{r-1}k = r(r-1)/2 = 0\), since \(k \mapsto 1/k\) permutes \(\mathbb{F}_r^\times\). So \(H_{r-1-i} = -\sum_{k=r-i}^{r-1}1/k = -\sum_{j=1}^{i}1/(r-j) = \sum_{j=1}^{i}1/j = H_i\).
  2. Apply 1 at \(i = 1, 2\).
  3. \(2h = r-1 = -1\), so \(1/h = 2/(2h) = -2\).
  4. Interchange the order of summation: \(\sum_{k=1}^{2n}(-1)^{k-1}H_k = \sum_{j=1}^{2n}\frac1j\sum_{k=j}^{2n}(-1)^{k-1}\). The inner sum is \(-1\) for even \(j\) and \(0\) for odd \(j\), so the total is \(-\sum_{j \text{ even}}1/j = -H_n/2\).
  5. Write \(H_i = \sum_{j\le i}1/j\) and interchange.

The doubling identity

Lemma 1 (unfolding). Write \(x = 2cj + t\) with \(j = \lfloor x/(2c)\rfloor\) and \(0 \le t \le 2c-1\), and put \(\varepsilon = \lfloor t/c \rfloor \in \{0,1\}\). Then

\[F(2x) = H_{2j+\varepsilon} \quad\text{for the full blocks } 0 \le j \le h-1, \qquad F(2x) = H_0 = 0 \quad\text{for } j = h.\]

Proof.

  1. \(2x = 4cj + 2t\) with \(t \le 2c-1\), so \(2t = 2c\varepsilon + (2t \bmod 2c)\) and \(\lfloor 2x/(2c)\rfloor = 2j+\varepsilon\). Also \(2j+\varepsilon \le 2h-1 = r-2\), so reflection (Lemma 0) applies.
  2. If \(2x > M\), write \(2x = 2cq + s\) with \(0 \le s \le 2c-1\). Then \(P - 2x = 2c(r-q)-1-s = 2c(r-q-1) + (2c-1-s)\), so the block index is \(r-q-1 = r-1-2j-\varepsilon\), whose \(H\)-value equals \(H_{2j+\varepsilon}\) by reflection.
  3. For \(j = h\) we have \(t \le c-1\), hence \(\varepsilon = 0\) and \(2x > M\), giving index \(r-1-2h = 0\).

Lemma 2 (block collapse). In \(\mathbb{F}_r\),

\[\frac{R(2)}{c} = \sum_{j=0}^{h-1} H_j\bigl(H_{2j}+H_{2j+1}\bigr) = \sum_{i=0}^{r-1} H_i H_{\lfloor i/2\rfloor}, \qquad \frac{R(1)}{c} = \sum_{i=0}^{r-1} H_i^2 .\]

Proof.

  1. \(F\) is constant on each block. For \(j \le h-1\) the block has \(2c\) elements, of which exactly \(c\) satisfy \(F(2x) = H_{2j}\) and \(c\) satisfy \(F(2x) = H_{2j+1}\), by Lemma 1. The last block contributes \(H_h \cdot cH_0 = 0\).
  2. Summing over \(j\) gives the middle expression. Since \(H_{r-1} = 0\) and the pairs \((i, \lfloor i/2\rfloor)\) for \(i = 0,\dots,r-1\) run through \((2j,j)\) and \((2j+1,j)\) for \(j \le h-1\), together with \((r-1,h)\), the third expression follows.
  3. For \(R(1)\): \(\sum_{x\in G}F(x)^2 = \sum_j H_j^2\,|\text{block }j|\) with sizes \(2c,\dots,2c,c\), and \(\sum_{i=0}^{r-1}H_i^2 = 2\sum_{i=0}^{h-1}H_i^2 + H_h^2\) by reflection.

Lemma 3 (harmonic defect). With \(D := \sum_{i=0}^{r-1} H_i\bigl(H_{\lfloor i/2\rfloor} - H_i\bigr)\) one has \(D \equiv H_h/2\) in \(\mathbb{F}_r\).

Proof.

  1. Reverse the summation. Since \(H_i - H_{\lfloor i/2\rfloor} = \sum_{l=\lfloor i/2\rfloor+1}^{i}1/l\) and \(l \le i \le 2l-1\), we get \(D = -\sum_{l=1}^{r-1}\frac1l\sum_{i=l}^{\min(2l-1,\,r-1)}H_i\).
  2. Split at \(l = h\). Put \(W(n) = \sum_{i=1}^{n}H_i = (n+1)H_n - n\) by Lemma 0(5). Since \(2l-1 \le r-2\) for \(l \le h\) and \(2l-1 \ge r\) for \(l \ge h+1\), the sum splits into \(l \le h\) and \(l > h\).
  3. First part. It equals \(-2O + W(h-1) + h\), where \(O := \sum_{l=1}^{h}H_{2l-1}\).
  4. Second part. It equals \(1 - W(h-1) + 1 + h\).
  5. Add. \(D \equiv -2O + 2h + 2\).
  6. Evaluate \(O\). \(W(2h-2) = (2h-1)H_{2h-2} - (2h-2) \equiv (-2)(3/2) + 3 = 0\) by Lemma 0(2). Splitting into even and odd parts \(E = \sum_{k=1}^{h-1}H_{2k}\), \(O' = \sum_{l=1}^{h-1}H_{2l-1}\), Lemma 0(4) gives \(O' - E = -H_{h-1}/2\), hence \(E = H_{h-1}/4\) and \(O = O' + H_{2h-1} = 1 - H_{h-1}/4\).
  7. Substitute. By Lemma 0(3), \(H_{h-1} = H_h + 2\). So \(D \equiv -2\bigl(1 - \tfrac{H_h+2}{4}\bigr) + 2h + 2 = 2h + \tfrac{H_h+2}{2} \equiv -1 + \tfrac{H_h}{2} + 1 = \tfrac{H_h}{2}\), using \(2h \equiv -1\).

Lemma 4 (Eisenstein 1850). \(H_h \equiv -2q_r(2) \pmod r\).

Proof.

  1. For \(1 \le k \le r-1\): \(\binom{r}{k} = \frac rk\binom{r-1}{k-1}\) and \(\binom{r-1}{k-1} = \prod_{i=1}^{k-1}\frac{r-i}{i!} \equiv (-1)^{k-1} \pmod r\), so \(\binom rk \equiv r(-1)^{k-1}/k \pmod{r^2}\).
  2. Evaluating \((1+x)^r\) at \(x=1\) modulo \(r^2\) gives \(2^r \equiv 2 + r\sum_{k=1}^{r-1}(-1)^{k-1}/k\).
  3. But \(2^r = 2\cdot 2^{r-1} = 2 + 2r\,q_r(2)\). Comparing 2 and 3 and dividing by \(r\): \(2q_r(2) \equiv \sum_{k=1}^{r-1}(-1)^{k-1}/k\).
  4. That alternating sum equals \(\sum_{\text{odd}}1/k - \sum_{\text{even}}1/k = \bigl(H_{r-1} - H_h/2\bigr) - H_h/2 = -H_h\), since \(\sum_{\text{even }k\le r-1}1/k = H_h/2\) and \(H_{r-1} = 0\).

Theorem 1 (The doubling identity) For every prime \(r > 3\), every \(c \ge 1\) and every prime \(P = 2cr-1\),

\[R(2) - R(1) = -c\,q_r(2) \qquad \text{in } \mathbb{F}_r .\]

No hypothesis on \(c\) is needed for the identity itself.

Figure 1: Every admissible \((r, c)\) pair with \(P = 2cr-1\) prime, for \(r \le 97\) and \(c \le 12\). Computed straight from the construction over \(G\), with no use of the identity. If the theorem were wrong these points would scatter.

Proof.

  1. Lemma 2 gives \(R(2) - R(1) = c\,D\), where \(D = \sum_i H_i(H_{\lfloor i/2\rfloor} - H_i)\).
  2. Lemma 3 gives \(D = H_h/2\).
  3. Lemma 4 gives \(H_h/2 = -q_r(2)\).

Theorem 2 (The Wieferich criterion) Let \(P = 2cr-1\) be prime and suppose \(r \nmid c\). Then

\[R(2) = R(1) \iff q_r(2) = 0 \iff r \text{ is a base-2 Wieferich prime}.\]

Proof.

  1. (\(\Leftarrow\)) If \(q_r(2) = 0\) then Theorem 1 gives \(R(2) = R(1)\), with no hypothesis on \(c\).
  2. (\(\Rightarrow\)) If \(R(2) = R(1)\) then \(c\,q_r(2) = 0\) in the field \(\mathbb{F}_r\); since \(r \nmid c\), \(c\) is invertible, so \(q_r(2) = 0\).
  3. Finally \(q_r(2) = 0 \iff 2^{r-1} \equiv 1 \pmod{r^2}\), the definition of a base-2 Wieferich prime.

The hypothesis \(r \nmid c\) cannot be dropped: by Lemma 2 both \(R(1)\) and \(R(2)\) are divisible by \(c\), so if \(r \mid c\) then \(R(1) = R(2) = 0\) identically while \(q_r(2)\) may be nonzero — for instance \((r,c,P) = (7,7,97)\) with \(q_7(2) = 2\).

Exact recovery

Theorem 3 (Recovery) If \(P = 2cr-1\) is prime and \(r \nmid c\), then the Fermat quotient is recovered exactly, not merely detected:

\[q_r(2) = -c^{-1}\bigl(R(2) - R(1)\bigr) \qquad \text{in } \mathbb{F}_r .\]

The recovery map is optimal: invertibility of \(c\) is necessary as well as sufficient.

The counting form needs no primality

Primality of \(P\) is needed only to read the sum as a correlation over the group \(G\). Defining

\[\tilde\rho(y) = \min\bigl(y \bmod P,\; P - (y \bmod P)\bigr), \quad \tilde F(x) = H_{\lfloor \tilde\rho(x)/(2c)\rfloor}, \quad \tilde R(a) = \sum_{x=1}^{M}\tilde F(x)\tilde F(\tilde\rho(ax)),\]

one has \(\tilde R(2) - \tilde R(1) = -c\,q_r(2)\) for every \(P = 2cr-1\), prime or composite, and \(\tilde R = R\) whenever \(P\) is prime. So the arithmetic statement is purely a lattice-point count; restricting to primes buys only the group-theoretic reading.

Scope: this works only for the doubling lag

The identity is not a general fact about multiplicative lags, and this is the sharpest part of the result.

  • General base fails. For \(a \ge 3\) the image of a full block under \(x \mapsto ax\) is the index interval \(\{aj,\dots,aj+a-1\}\), which for \(a \ge 3\) either carries non-uniform weights (if \(a \nmid 2c\)) or wraps the index circle. For \(a = 2\) the image is exactly two half-blocks and never wraps — \(2\) is the unique non-wrapping multiplier. Explicitly, at \((r,c) = (7,1)\): \(a = 3\) gives \(R(3) - R(1) = 2\) while \(-c\,q_7(3) = 1\).
  • No iteration. \(R(2^k) - R(1) = -ck\,q_r(2)\) already fails at \(k = 2\): at \((r,c) = (7,1)\), \(R(4)-R(1) = 2\) while \(-2c\,q_7(2) = 3\).
  • Well-posedness. \(q_r(a)\) lives on \((\mathbb{Z}/r^2)^\times\) and is not a function of \(a \bmod r\) (e.g. \(q_5(2) = 3\) but \(q_5(7) = 0\)), whereas \(R(a)\) depends only on \(a \bmod \pm P\). So no general-base identity of this shape is even well posed.
  • What is recovered: \(q_r(2^k) = k\,q_r(2)\) for all integers \(k\), by multiplicativity of \(q_r\).

One caution, in the interest of not overclaiming: the assertion that \(2\) is the only multiplier for which the defect collapses does not follow from non-wrapping alone, and would be false if read as “only \(a = 2\) satisfies the identity” — the source’s own computations list \(a = 3\) inside the success set for \((r,c) = (19,3)\) and \((7,3)\). Only uniqueness of the non-wrapping multiplier is claimed here.

Verification

Every figure in this table comes from sweeping the construction, never from the identity it is meant to confirm. The verification script reproduces a representative subset from scratch and stops on any disagreement: 276 admissible \((r, c)\) pairs over 23 primes, 69 composite-\(P\) pairs, and both known Wieferich primes, where it recovers \(R(1) = R(2) = 1073\) at \(r = 1093\) and \(3503\) at \(r = 3511\).

what cases result
identity at definition level, \(r < 300\), \(cr \le 3000\) 1,424 0 mismatches
identity via the closed form, all primes \(r < 5000\) 26,948 0 mismatches
identity at definition level, random primes \(10^4 \le r \le 4\cdot10^6\) 14 0 mismatches
independent PARI/GP implementation from the definition 1,621 0 mismatches
proof steps (L1)–(L9), all primes \(5 \le r < 3000\) 428 primes 0 failures
counting form for composite \(P\) 4,008 0 mismatches (group form only 82/4,008, as expected)
period independence (\(2\) not primitive mod \(P\)) 687 0 mismatches
known Wieferich primes \(1093\) (\(c{=}10\)) and \(3511\) (\(c{=}4\)) 2 + controls \(R(1) = R(2)\) exactly, \(q_r(2) = 0\)
predicted failure when \(r \mid c\) 28 28 — all of them, as predicted

Note the last two rows: the negative results are predicted failures that were then observed, and the counterexample hunts for \(a \ge 3\) and for \(k=2\) produce explicit witnesses. Nothing here rests on “we searched and found nothing”.

Machine-checked. The counting form is also proved in Lean: the doubling identity, the criterion, and Eisenstein’s congruence, with nothing assumed. It covers the sum over the integer window \([1,M]\); the group form over \(G\) follows through a bijection that is not itself formalized.