Past exam of the probability, statistics and options I course of the University of Oxford / 2009 / C (Number Theory)

Fermat's little theorem states that for a prime $p$ and any integer $a$,If $p\nmid a$, the equivalent multiplicative form is $a^{p-1}\equiv 1(\mathrm{mod}p)$.

Wilson's theorem states that an integer $p>1$ is prime if and only ifIn particular the congruence holds for every prime $p$, including two.

Combine the preceding congruences: $a^p\equiv a$ and $(p-1)!\equiv -1(\mathrm{mod}p)$. Therefore $a^p+(p-1)!a\equiv a-a=0$, and $(p-1)!a^p+a\equiv -a+a=0$. This proves both stated divisibilities for every integer $a$, with no assumption that $a$ is coprime to $p$.

Modulo $p$, the term $p^{q-1}$ is zero and Fermat's little theorem gives $q^{p-1}\equiv 1$, since $q\ne p$. Modulo $q$, the roles reverse. Hence the sum minus one is divisible by both distinct primes. Their coprimality gives