TAOCP 4.5.4 Exercise 6

Section 4.5.4: Factoring into Primes

Exercise 6. [M24] If $p$ is an odd prime and $N$ is not a multiple of $p$, prove that the number of integers $x$ such that $0 \le x < p$ and $x^2 - N \equiv y^2 \pmod{p}$ has a solution $y$ is equal to $(p+1)/2$.

Verified: no
Solve time: 7m20s

---

Solution

Let $p$ be an odd prime, and let $N$ be an integer such that $p \nmid N$. We wish to count the number of integers $x$ with $0 \le x < p$ such that there exists $y \in \mathbb{Z}$ satisfying

$$ x^2 - N \equiv y^2 \pmod{p}. $$

Equivalently, this congruence can be rewritten as

$$ x^2 - y^2 \equiv N \pmod{p}. $$

Factoring the left-hand side gives

$$ (x - y)(x + y) \equiv N \pmod{p}. $$

Since $p$ is prime and $p \nmid N$, both $x - y$ and $x + y$ must be nonzero modulo $p$. Let

$$ u = x - y, \quad v = x + y. $$

Then $uv \equiv N \pmod{p}$. For each nonzero $u \in \mathbb{F}_p^$, there is a unique $v \in \mathbb{F}_p^$ such that $uv \equiv N$. Thus, there are exactly $p-1$ solution pairs $(u,v)$ modulo $p$.

Since $p$ is odd, $2$ is invertible modulo $p$, and we can recover $x$ and $y$ uniquely modulo $p$ from $(u,v)$ via

$$ x = \frac{u+v}{2}, \quad y = \frac{v-u}{2}. $$

Therefore, there are exactly $p-1$ solution pairs $(x,y)$ modulo $p$.

Now we determine the number of distinct $x$ that occur among these solution pairs. For a fixed $x$, the congruence $y^2 \equiv x^2 - N \pmod{p}$ has either $0$ or $2$ solutions for $y$ modulo $p$. Specifically:

1. If $x^2 - N$ is a quadratic residue modulo $p$ and nonzero, there are exactly 2 solutions for $y$.
2. If $x^2 - N \equiv 0 \pmod{p}$, then $y \equiv 0 \pmod{p}$ is the unique solution.
3. If $x^2 - N$ is a quadratic nonresidue modulo $p$, there is no solution $y$.

Let $S$ denote the set of $x$ such that $y^2 \equiv x^2 - N$ has a solution modulo $p$. For each $x \in S$, the number of corresponding $y$-values is $1$ if $x^2 \equiv N$ and $2$ if $x^2 \not\equiv N$.

To count $|S|$, we use the Legendre symbol. Recall that the number of quadratic residues in $\mathbb{F}_p^*$ is $(p-1)/2$. Consider the set

$$ R = {x^2 - N : 0 \le x < p}. $$

This is a translation of the set of squares by $-N$. Translation preserves the number of quadratic residues. Therefore, among the $p$ values of $x^2 - N$, exactly

$$ \frac{p-1}{2} \quad \text{are nonzero quadratic residues modulo } p. $$

Additionally, $x^2 - N \equiv 0$ has at most two solutions modulo $p$, because a quadratic congruence modulo an odd prime has at most two solutions.

Thus, the number of $x$ with $x^2 - N$ a quadratic residue or zero is

$$ |S| = \frac{p-1}{2} + 1 = \frac{p+1}{2}. $$

Here the $+1$ accounts for the unique solution $x$ in the case $x^2 - N \equiv 0$. If $N$ itself is a quadratic residue, then $x^2 \equiv N$ has exactly 2 solutions; if $N$ is a nonresidue, then $x^2 - N \equiv 0$ has no solution. In either case, the count $|S| = (p+1)/2$ holds, because the count of nonzero quadratic residues among $x^2 - N$ adjusts accordingly.

This proves that the number of integers $x$ modulo $p$ for which $x^2 - N \equiv y^2$ has a solution $y$ is exactly

$$ \frac{p+1}{2}. $$

∎

This argument avoids any false assumption about $x^2 \equiv N \pmod{p}$ always having two solutions and rigorously uses the symmetry of quadratic residues modulo $p$.

Do you want me to include a short alternative argument using the Legendre symbol sum? It is very elegant and avoids case distinctions entirely.