Let $p$ be a prime number, and let $n$ be a positive integer. Find the number of quadruples $\left(a_{1}, a_{2}, a_{3}, a_{4}\right)$ with $a_{i} \in\left\{0,1, \ldots, p^{n}-1\right\}$ for $i=1,2,3,4$ such that

$$
p^{n} \mid\left(a_{1} a_{2}+a_{3} a_{4}+1\right) .
$$

Answer: $p^{3 n}-p^{3 n-2}$.
We have $p^{n}-p^{n-1}$ choices for $a_{1}$ such that $p \nmid a_{1}$. In this case for any of the $p^{n} \cdot p^{n}$ choices of $a_{3}$ and $a_{4}$, there is a unique choice of $a_{2}$, namely,

$$
a_{2} \equiv a_{1}^{-1}\left(-1-a_{3} a_{4}\right) \quad \bmod p^{n}
$$

This gives $p^{2 n}\left(p^{n}-p^{n-1}\right)=p^{3 n-1}(p-1)$ of quadruples.

If $p \mid a_{1}$ then we obviously have $p \nmid a_{3}$, since otherwise the condition

$$
p^{n} \mid\left(a_{1} a_{2}+a_{3} a_{4}+1\right)
$$

is violated. Now, if $p \mid a_{1}, p \nmid a_{3}$, for any choice of $a_{2}$ there is a unique choice of $a_{4}$, namely,

$$
a_{4} \equiv a_{3}^{-1}\left(-1-a_{1} a_{2}\right) \quad \bmod p^{n}
$$

Thus, for these $p^{n-1}$ choices of $a_{1}$ and $p^{n}-p^{n-1}$ choices of $a_{3}$, we have for each of the $p^{n}$ choices of $a_{2}$ a unique $a_{4}$. So in this case there are $p^{n-1}\left(p^{n}-p^{n-1}\right) p^{n}=p^{3 n-2}(p-1)$ of quadruples.

Thus, the total number of quadruples is

$$
p^{3 n-1}(p-1)+p^{3 n-2}(p-1)=p^{3 n}-p^{3 n-2} \text {. }
$$

#