Vietnamese Mathematical Olympiad

For any integer $k$, let $N_k$ be the number of ordered 6-tuple $(a, b, c, a', b', c')$ that satisfy
$$ab + a'b' \equiv bc + b'c' \equiv ca + c'a' \equiv 1 \pmod{k}$$
and $a, b, c, a', b', c' \in \{0, 1, \dots, k-1\}$. By the Chinese Remainder Theorem,
$$N_{mn} = N_n \times N_m \text{ if } \gcd(n, m) = 1.$$
Therefore, in order to compute $N_{15}$, we only need to compute $N_3$ and $N_5$. We will compute $N_p$ for any $p$ prime. Fix a solution $(a, b, a', b')$ of the equation $ab + a'b' \equiv 1 \pmod{p}$, we compute the number of solutions of the following system
$$bc + b'c' \equiv ca + c'a' \equiv 1 \pmod{p} \quad (1)$$
We consider three cases

* Suppose that $(a, a') \neq t(b, b') \pmod{p}$ for any $t \in \{0, 1, \dots, p-1\}$. Then the system (1) has a unique solution
$$c \equiv \frac{a' - b'}{a'b - b'a}, \quad c' \equiv \frac{a - b}{ab' - ba'} \pmod{p}$$
* Suppose that $(a, a') \equiv t(b, b') \pmod{p}$ for some $t \neq 1$. Then the system (1) has no solution.
* Suppose that $(a, a') \equiv (b, b') \pmod{p}$. Then the system (1) becomes a single equation $bc + b'c' \equiv 1 \pmod{p}$. Since $ba + b'a' \equiv 1 \pmod{p}$, we can assume that $b \neq 0$. Hence, for any choice of $c'$, we have only one choice of $c \equiv (1 - b'c')/b \pmod{p}$. This implies that the system (1) has exactly $p$ solutions.

Let $T_p$ be the number of ordered tuples $(a, b, a', b')$ that satisfy $ab + a'b' \equiv 1 \pmod{p}$ and $a, b, a', b' \in \{0, 1, \dots, p-1\}$. For any pair $(a, a') \neq (0, 0)$, there are exactly $p$ pairs $(b, b')$ satisfy the equation. Hence, $T_p = p(p^2 - 1)$.

Let $C_p(t)$ be the number of ordered pairs $(a, b)$ that satisfy $a^2 + b^2 \equiv t \pmod{p}$ and $a, b \in \{0, 1, \dots, p-1\}$. From the above arguments, we have
$$N_p = T_p - \sum_{t=1}^{p-1} C_p(t) + pC_p(1) = p(p^2 - 1) - p^2 + C_p(0) + pC_p(1).$$
It is easy to get $C_3(0) = 1, C_3(1) = 4, C_5(0) = 9, C_5(1) = 4$, which implies that $N_3 = 28, N_5 = 124$ and $N_{15} = 28 \times 124 = 3472$.

Therefore, the number of ordered 6-tuple satisfying the given conditions is 3472. ☐