Timeline for Shifting quadratic residues

5 events

when toggle format	what		by	license	comment
May 24, 2019 at 9:44	vote	accept	doe
May 23, 2019 at 19:14	answer	added	Fedor Petrov		timeline score: 2
May 23, 2019 at 19:08	comment	added	KConrad		That's presumably where the division by 4 is coming from. I don't have time to deal with the bookkeeping issues involved, but the "basic fact" you couldn't find is just that hyperbolas $x^2 - y^2 \equiv a \bmod p$ for odd prime $p$ and $a \not\equiv 0 \bmod p$ each have the same number of solutions (independent of $a$). The book of Ireland & Rosen has nice coverage of the general topic of counting solutions to equations over finite fields, especially "diagonal" equations like the hyperbola (no monomials involve more than one variable). Your question is more suitable for math.stackexchange.
May 23, 2019 at 19:04	comment	added	KConrad		Looking at $G_0 \cap G_a$ is close to counting solutions to $x^2 \equiv a + y^2 \bmod p$, so $x^2 - y^2 \equiv a \bmod p$. For odd prime $p$, making the change of variables $u = x + y \bmod p$ and $v = x - y \bmod p$, that would be counting solutions to $uv \equiv a \bmod p$. For $a \not\equiv 0 \bmod p$ there are obviously $p-1$ solutions (for each choice of nonzero $u$ there is one $v$). Since you're counting squares with a property rather than numbers whose squares have a property there is some double sign issue to account for ($x^2$ and $y^2$ arise from 2 choices each unless one is 0).
May 23, 2019 at 18:37	history	asked	doe	CC BY-SA 4.0