Prove that alternating signs never collide in hash table Wikipedia says something surprising: if we are using quadratic hashing, we can alternate the sign of the offset to avoid collisions. I can't find any counterexamples, but I can't prove it, either.
I've simplified the question to this:
Given that $M$ is a prime number, and $M \equiv 3\ (\textrm{mod}\ 4)$,
Can you prove that the function $h(k) = (-1)^k k^2 (\textrm{mod}\ M)$ is injective over the domain of integers from $0$ to $M - 1$? (Can you prove that every input maps to a distinct output?)
See also: https://stackoverflow.com/questions/49074806/preventing-secondary-clustering-in-quadratic-probing-proof
 A: This just expands on lulu's answer. (Note: if the $\text{mod}$ is left out, assume $\pmod M$).
First, notice that for a prime modulus $M$, every residue has exactly two roots. Every residue is congruent to $r^2$ for some $r$. To prove that the only solutions to $x^2\equiv r^2$ are $r$ and $-r$ and there is no third solution, we can factor to $(x-r)(x+r)\equiv 0$. If $x$ is not equal to $r$ or $-r$, then the left hand side is the product of two nonzero numbers, which is nonzero modulo a prime number (this is not true if $M$ is not prime, e.g. $3\cdot 3\equiv 0\pmod 9$, which leads to the counterexample in the comments).
Thus, if $l$ and $k$ are collisions of the same parity, we would have $l^2\equiv k^2$, which would imply $l=M-k$, but that is impossible as they are of the same parity and $M$ is odd.
Similarly, if they were collisions of opposite parity, then $-k^2\equiv l^2$. Then multiplying by $\left(k^{-1}\right)^2$ on both sides, $-1\equiv \left(l\cdot k^{-1}\right)^2$, which is impossible when $M\equiv 3\pmod 4$.
