. Find all pairs of prime numbers $(p, q)$ such that:

$$
x^{3 p q} \equiv x \quad(\bmod 3 p q)
$$

for all integers $x$.
. By symmetry of roles, we can assume $p \leqslant q$. We have $2^{3 p q} \equiv 2 \pmod{3}$, which implies that $p$ and $q$ are odd (otherwise $2^{3 p q}$ would be congruent to 1). Since $q$ is prime, we have $x^{3 p q-1} \equiv 1 \pmod{q}$. Recall the following result ${ }^{13}$: there exists an integer $x$ such that for all $n$, we have:

$$
x^{n} \equiv 1 \pmod{q} \quad \Longleftrightarrow \quad n \text{ is a multiple of } q-1
$$

From this result and the previous congruence, we deduce that $q-1$ divides $3 p q-1$. Furthermore, $3 p q - 1 - 3 p(q-1) = 3 p - 1$, so $q-1$ divides $3 p - 1$, and similarly, $p-1$ divides $3 q - 1$. Suppose that $p = q$. In this case, $p-1$ divides $3 p - 1$, but $3 p - 1 - 3(p-1) = 2$ so $p-1$ divides 2, hence $p = q = 3$. But $4^{27} \equiv 1 \pmod{27}$, so $(3,3)$ is not a solution. Therefore, $p \neq q$. Without loss of generality, we can assume $p < q$. Then, since $p$ and $q$ are odd, we have $q \geqslant p + 2$, and thus the integer $\frac{3 p - 1}{q - 1}$ is strictly less than 3. Moreover, it is clearly different from 1, and is therefore equal to 2, i.e., $2 q = 3 p + 1$. Since $p-1$ divides $3 q - 1$, it also divides $6 q - 2 = 9 p + 1$ and thus $(9 p + 1) - 9(p - 1) = 10$. This leaves the two possibilities $(3,5)$ and $(11,17)$. But $3^{45} \equiv 0 \pmod{45}$, so $(3,5)$ is not a solution to the problem. Finally, let's show that $(11,17)$ is a solution. According to the Chinese Remainder Theorem, it suffices to show that $x^{3 \times 11 \times 17} \equiv x \pmod{3}$, $x^{3 \times 11 \times 17} \equiv x \pmod{11}$, and $x^{3 \times 11 \times 17} \equiv x \pmod{17}$. We have $3 \times 11 \times 17 \equiv 1 \pmod{2}$; for $x \not\equiv 0 \pmod{3}$, we have $x^{2} \equiv 1 \pmod{3}$, so $x^{3 \times 11 \times 17} \equiv x \pmod{3}$, and this is also true for $x \equiv 0 \pmod{3}$. Similarly, we have $3 \times 11 \times 17 \equiv 1 \pmod{10}$, $x^{10} \equiv 1 \pmod{11}$ for $x \not\equiv 0 \pmod{11}$, so $x^{3 \times 11 \times 17} \equiv x \pmod{11}$, and $3 \times 11 \times 17 \equiv 1 \pmod{16}$, $x^{16} \equiv 1 \pmod{17}$ for $x \not\equiv 0 \pmod{17}$, so $x^{3 \times 11 \times 17} \equiv x \pmod{17}$, which concludes: the solutions are the pairs $(11,17)$ and $(17,11)$. Remark. The composite integers $n$ satisfying $x^{n} \equiv x \pmod{n}$ for all $n$ are called Carmichael numbers. The one in the exercise $3 \times 11 \times 17 = 561$ is the smallest and most well-known, and as we have just shown, it is the only one of the form $3 p q$ with $p$ and $q$ primes. It is known today that there are infinitely many Carmichael numbers.