How many distinct values can $x^{9}$ take modulo 999?
First, let's decompose $999=37 \times 27$. Knowing the values modulo 37 and those modulo 27, we can deduce those modulo 999.

Modulo 37, for $x$ non-zero, $\left(x^{9}\right)^{4} \equiv x^{36} \equiv 1$. There are only two values of $x$ modulo 37 such that $x^{2} \equiv 1$ since $x^{2}-1=(x-1)(x+1): x \equiv 1$ and $x \equiv -1$ (equiv 36). Similarly, there are only two values modulo 37 such that $x^{2} \equiv 36: 6$ and -6. Therefore, there are four values such that $x^{4} \equiv 1: x \equiv 1, -1, 6, -6$. Thus, $x^{9}$ can only take five values modulo 37: 1, -1, 6, -6, and 0! which should not be forgotten.

Modulo 27, we use the binomial formula: $(a+b)^{n}=a^{n}+n a^{n-1} b + \frac{n(n-1)}{2} a^{n-2} b^{2}+\cdots$ to show that $(a+3 k)^{9} \equiv a^{9}(\bmod 27)$. Therefore, $a^{9}$ can only take three values modulo 27: 0, 1, and -1 (equiv 26).

Thus, modulo 999, $x^{9}$ can only take $3 \times 5 = 15$ distinct values. To determine them, we need to perform the calculation from exercise 4 fifteen times for all pairs of integers, the first in $\{0, 1, -1, 6, -6\}$ modulo 37, the second in $\{0, 1, -1\}$ modulo 27. Since the Bézout relation is the same for all calculations, it is relatively quick. We obtain, modulo 999 (which was not explicitly required): $0, 703, 296, 297, 1, 593, 702, 406, 998, 783, 487, 80, 216, 919, 512$.

## Wilson's Theorem

If $p$ is a prime number, $(p-1)!\equiv-1(\bmod p)$. If $p$ is not prime but $>5, (p-1)!\equiv 0(\bmod p)$.

## Proof

Recall that $n!=n \times(n-1) \times(n-2) \times \cdots \times 2 \times 1$. If $p$ is not prime, it can be written as $a \times b$ where $a$ and $b$ both appear in the product $(p-1)!$. If $a=b>2, a$ and $2a$ both appear in the product $(p-1)!$, which is therefore divisible by $a^{2}=p$. Note that the result is false for $p=4$.

For $p$ prime, the elements $\{1, 2, \cdots, p-1\}$ of $\mathbb{Z} / p \mathbb{Z}$ are all invertible, meaning that for every $x$, there exists $y$ such that $x y \equiv 1(\bmod p)$. 1 and -1 (equiv $p-1$) are their own inverses. In contrast, every other element of $\mathbb{Z} / p \mathbb{Z}$ is distinct from its inverse, as we saw in exercise 4, $x^{2}=1$ has only two roots, 1 and -1 in $\mathbb{Z} / p \mathbb{Z}$. These elements can therefore be paired such that the product of each pair is 1. Since $(p-1)!$ is the product of 1, -1, and each of these pairs, it is congruent to -1 modulo $p$.

## Squares modulo 4

It is important to know that the square of an integer can only be congruent to 0 or 1 modulo 4, never to 2 or 3. However, we can even note that modulo 8, the square of an odd number is always congruent to 1, and the square of an even number is congruent to 0 or 4. This allows us to handle the following exercise: