8.68 $n$ is a given positive integer, how many perfect squares are there modulo $n$?
(British Mathematical Olympiad, 1994)
[Solution] Let $A_{n}$ denote the number of perfect squares modulo $2^{n}$.
Obviously, for $\bmod 2$, there are 0, 1 two perfect squares,
for $\bmod 2^{2}=\bmod 4$, there are also 0, 1 two perfect squares.
Thus, we have $A_{1}=2, A_{2}=2$.
For $n \geqslant 3$, we prove that $A_{n}=2^{n-3}+A_{n-2}$
Let $a, b$ be odd numbers, $0<a<2^{n}, 0<b<2^{n}$, and satisfy
$$
a^{2} \equiv b^{2}\left(\bmod 2^{n}\right),
$$

which means
$$
(a+b)(a-b) \equiv 0\left(\bmod 2^{n}\right).
$$

Since $a, b$ are odd, then $a-b, a+b$ are both even. Considering $\bmod 4$, since odd numbers are of the form $4k+1$ or $4k+3$, $a-b$ and $a+b$ cannot both be multiples of 4. Therefore, one of $a-b$ and $a+b$ must be a multiple of 2 but not a multiple of 4. This implies

or
$$
\begin{array}{c}
a-b \equiv 0\left(\bmod 2^{n-1}\right) \\
a+b \equiv 0\left(\bmod 2^{n-1}\right).
\end{array}
$$

Thus, $b \equiv a\left(\bmod 2^{n}\right)$ or $b \equiv -a\left(\bmod 2^{n-1}\right)$.
Using $0<a<2^{n}, 0<b<2^{n}$ and the above, we have
$$
b \equiv a\left(\bmod 2^{n}\right), b \equiv 2^{n-1}+a\left(\bmod 2^{n}\right).
$$

or $\quad b \equiv 2^{n-1}-a(\bmod 2 n)$, and $b \equiv 2^{n}-a\left(\bmod 2^{n}\right)$.
Since $a$ is odd, when $n \geqslant 3$, the four positive integers $a$, $2^{n-1}+a$, $2^{n-1}-a$, $2^{n}-a$ on the right side of the above four congruences are all distinct. There are $2^{n-1}$ odd numbers greater than or equal to 1 and less than $2^{n}$. Among these $2^{n-1}$ odd numbers, taking any one as $a$, for this $a$, there are 4 numbers $b$ that satisfy $a^{2} \equiv b^{2}\left(\bmod 2^{n}\right)$, i.e., $b = a, b = 2^{n}-a, b \equiv 2^{n-1}+a\left(\bmod 2^{n}\right), b \equiv 2^{n-1}-a\left(\bmod 2^{n}\right)$. Therefore, these $2^{n-1}$ odd numbers can be grouped into 4 odd numbers per group, totaling $\frac{2^{n-1}}{4}=2^{n-3}$ groups. For different groups, $a^{2} \equiv b^{2}\left(\bmod 2^{n}\right)$ does not hold. Therefore, in the case of odd numbers, the number of such numbers is $2^{n-3}$.
In the case of even numbers, let even numbers $2a, 2b, 0 \leqslant 2a < 2^{n}, 0 \leqslant 2b < 2^{n}$, satisfy
$$
(2a)^{2} \equiv (2b)^{2}\left(\bmod 2^{n}\right).
$$

Thus, $0 \leqslant a < 2^{n-1}, 0 \leqslant b < 2^{n-1}$, and
$$
a^{2} \equiv b^{2}\left(\bmod 2^{n-2}\right).
$$

Since when $2^{n-1} \leqslant 2a < 2^{n}, 2^{n-1} \leqslant 2b < 2^{n}$, we have
$$
\begin{array}{l}
\left(2a-2^{n-1}\right)^{2} \equiv (2a)^{2}\left(\bmod 2^{n}\right), \\
\left(2b-2^{n-1}\right)^{2} \equiv (2b)^{2}\left(\bmod 2^{n}\right),
\end{array}
$$

we only need to consider the case $0 \leqslant 2a < 2^{n-1}, 0 \leqslant 2b < 2^{n-1}$.
At this point, the number of perfect squares modulo $2^{n-2}$ corresponds one-to-one with the number of even perfect squares modulo $2^{n}$. Therefore, formula (1) holds.
In formula (1), when $n$ is even, we have
$$
\begin{array}{l}
A_{2k} = 2^{2k-3} + A_{2k-2}, A_{2k-2} = 2^{2k-5} + A_{2k-4}, \\
A_{2k-4} = 2^{2k-7} + A_{2k-6}, \cdots \cdots \\
A_{6} = 2^{3} + A_{4}, A_{4} = 2 + A_{2}.
\end{array}
$$

Adding the above $k-1$ equations, we get
$$
\begin{aligned}
A_{2k} & = \left(2 + 2^{3} + \cdots + 2^{2k-5} + 2^{2k-3}\right) + A_{2} \\
& = \frac{1}{3}\left(2^{2k-1} - 2\right) + 2 \\
& = \frac{1}{3}\left(2^{2k-1} + 4\right).
\end{aligned}
$$

When $n$ is odd, we have
$$
\begin{aligned}
A_{2k+1} & = 2^{2k-2} + A_{2k-1}, A_{2k-1} = 2^{2k-4} + A_{2k-3}, \\
A_{2k-3} & = 2^{2k-6} + A_{2k-5}, \cdots \cdots \\
A_{5} & = 2^{2} + A_{3}, A_{3} = 2^{0} + A_{1},
\end{aligned}
$$

Adding the above equations, we get
$$
A_{2k+1} = \left(2^{0} + 2^{2} + \cdots + 2^{2k-4} + 2^{2k-2}\right) + 2 = \frac{1}{3}\left(2^{2k} + 5\right).
$$

Thus, we have $A_{n} = \left\{\begin{array}{l}\frac{1}{3}\left(2^{n-1} + 4\right), n \text{ is even,} \\ \frac{1}{3}\left(2^{n-1} + 5\right), n \text{ is odd.}\end{array}\right.$