Past exam of the options I course of the University of Oxford / 2009 / C / C1

Fermat's little theorem says that for a prime number $p$ and any integer $a$,If $p\nmid a$, cancellation gives the equivalent statement $a^{p-1}\equiv 1(\mathrm{mod}p)$.

Wilson's theorem states that an integer $p>1$ is a prime number if and only ifIn particular this holds for every prime, including $p=2$.

Apply Fermat's little theorem and Wilson's theorem in the ring of integers modulo n with modulus $p$. They giveA vanishing modular congruence modulo $p$ is precisely divisibility by $p$, so both divisibilities hold, without requiring $p\nmid a$.

Because the primes are distinct, Fermat's little theorem gives $q^{p-1}\equiv 1(\mathrm{mod}p)$ and $p^{q-1}\equiv 1(\mathrm{mod}q)$. The other term in each modulus vanishes. ThereforeThe distinct primes are coprime, so their product divides this integer. Hence