Past exam of the mathematics course of the University of Cambridge / 2007 / ia / Paper 4 / 8E / ii / Solution

The Fermat-Euler theorem states that, for a positive integer $q$ and an integer $a$ coprime to $q$, $a^{\phi (q)}\equiv 1(\mathrm{mod}q)$, where the Euler totient function $\phi (q)$ counts residue classes coprime to $q$. The case $q=1$ is trivial. For $q>1$, let $r_1,\dots ,r_{\phi (q)}$ be a reduced residue system. Multiplication by $a$ permutes it: equality of two resulting residues can be cancelled using the modular inverse of $a$, and the products remain coprime to $q$. Multiplying the residues before and after the permutation givesEvery factor on the right is a unit, so its product can be cancelled. This provesThe integer $359$ is prime: none of the primes $2,3,5,7,11,13,17$ up to $\sqrt{359}<19$ divides it. Therefore $\phi (359)=358$. Apply the theorem to $60$ and use the supplied congruence:To connect this to individual digits rather than merely assert periodicity, use long-division remainders $r_0=1$ andInduction gives $r_n\equiv 10^n(\mathrm{mod}359)$. Since $10$ is coprime to $359$, no remainder is zero. The congruence above therefore implies $r_{n+179}=r_n$ for every $n\ge 0$, using the unique representative in $1,\dots ,358$. In particularHenceThis is the mechanism of decimal period from multiplicative order: the period divides $179$.