Past exam of the mathematics course of the University of Cambridge / 2010 / ia / Paper 4 / 6E / Solution

The Fermat little theorem states that if $p$ is a prime number, then $a^p\equiv a(\mathrm{mod}p)$ for every integer $a$. Equivalently, for $p\nmid a$, $a^{p-1}\equiv 1(\mathrm{mod}p)$.

To prove it when $p\nmid a$, multiplication by $a$ permutes the nonzero residues $1,\dots ,p-1$. Indeed, $ai\equiv aj(\mathrm{mod}p)$ implies $p\mid a(i-j)$, and the Euclid lemma implies $i=j$ in this range. Multiplying all these residues givesNone of the factors of $(p-1)!$ is divisible by $p$, so the factorial has a modular inverse. Cancelling it proves $a^{p-1}\equiv 1$, hence $a^p\equiv a$. When $p\mid a$, the latter identity has both sides zero, completing the proof.

For an odd prime number $p\ne 5$, the numbers $10,p$ are coprime. The Fermat little theorem gives $10^{p-1}\equiv 1(\mathrm{mod}p)$, and consequentlyThese exponents are distinct, so infinitely many are obtained.

Write the repdigit with $n$ copies of $5$ asIf $p\ne 3,5$, choose $n$ to be any positive multiple of $p-1$. Then $9$ has a modular inverse modulo $p$, so $p\mid R_n$. Division by $9$ cannot be used modulo $3$; instead $10\equiv 1(\mathrm{mod}3)$ gives $R_n\equiv 5n(\mathrm{mod}3)$, so $3\mid R_{3j}$ for every $j\ge 1$. If $p=5$, every $R_n$ is divisible by $5$. ThusThe separate treatment of $3$ accounts for the prime factor of the geometric-sum denominator.