Achievement GET: max out the title character limit exactly!

Okay so this isn't algebra but it was an omitted substep of an omitted substep of a step in a crazy solution to a trigonometric-function problem.



Let be an odd prime (actually in the problem so the cases at the end weren't needed); below, we are working entirely under residue classes with extremely sloppy terminology.

Lemma. For each which is a quadratic residue, excluding , and each which is a quadratic nonresidue, compute . Then each nonzero value is attained by equally many times, explicitly, .

Proof. Let be a primitive root. Then it is certainly not a quadratic residue (or would never attain a nonresidue). So if is a residue and is not, then is a residue and is not.

This way we can map each pair with sum to with sum , and this mapping is also clearly reversible ( exists), and therefore bijective. So each sum appears as many times as , so the sum appears as many times as , and since will attain every nonzero value, each nonzero sum appears equally many times.

To get the formula just count how many times is attained: if is of the form then is a quadratic residue so are both residues or both nonresidues and will never appear; if is of the form then is a nonresidue, so appears for each residue , of which there are .

The total number of pairs is ; the total number of pairs with nonzero sum is that minus if ; subtract if applicable, divide by the nonzero sums, and insert a floor function randomly so that we don't have to give a function with cases to get the result.