Example 5 Find the number of ordered integer pairs $(a, b)$ such that
$$
x^{2}+a x+b=167 y
$$

has integer solutions $(x, y)$, where $1 \leqslant a, b \leqslant 2004 .^{[4]}$ (2004, Singapore Mathematical Olympiad)
If $x^{2}+a x+b \equiv 0(\bmod 167)$, then completing the square gives
$$
a^{2}-4 b \equiv(2 x+a)^{2}(\bmod 167) .
$$

Therefore, for a fixed $a$, $a^{2}-4 b$ is a quadratic residue modulo 167.

Hence, by the lemma, $b$ can take $\frac{167-1}{2}+1=84$ values modulo 167.

And $\frac{2004}{167}=12$, so each $a$ corresponds to $84 \times 12$ values of $b$, totaling
$$
2004 \times 84 \times 12=2020032
$$

ordered integer solutions.
The lemma can lead to the important Euler's criterion.
Theorem 3 (Euler's criterion) Let $p$ be an odd prime. Then
$$
a^{\frac{p-1}{2}} \equiv\left(\frac{a}{p}\right)(\bmod p) \text {. }
$$

Proof: Take a primitive root of $p$ to be $g$, so the residue system $\{1,2, \cdots, p-1\}$ can be represented as
$$
\left\{g, \cdots, g^{p-2}, g^{p-1}=1\right\} \text {. }
$$

By the lemma, there are exactly $\frac{p-1}{2}$ quadratic residues.
Notice that, $g^{2 k}\left(1 \leqslant k \leqslant \frac{p-1}{2}\right)$ has an even exponent and must be a quadratic residue. Therefore, exactly the even powers of $g$ are quadratic residues, and the odd powers are quadratic non-residues.
Thus, when $\left(\frac{a}{p}\right)=1$,
$a^{\frac{p-1}{2}} \equiv\left(g^{2 k}\right)^{\frac{p-1}{2}} \equiv 1(\bmod p) ;$
when $\left(\frac{a}{p}\right)=-1$,
$$
a^{\frac{p-1}{2}} \equiv\left(g^{2 k+1}\right)^{\frac{p-1}{2}} \equiv g^{\frac{p-1}{2}} \equiv-1(\bmod p) \text {. }
$$

The last equation is due to
$$
g^{p-1} \equiv 1(\bmod p) \Rightarrow g^{\frac{p-1}{2}} \equiv \pm 1(\bmod p),
$$

and since $g$ is a primitive root with order $p-1$, it must be
$$
g^{\frac{p-1}{2}} \equiv -1(\bmod p) \text {. }
$$

Since each quadratic residue modulo $p$ can be characterized by a power of a primitive root of $p$, it is easy to see that the Legendre symbol is multiplicative.