Past exam of the mathematics course of the University of Cambridge / 2007 / ia / Paper 5 / 12 / ii

The Fermat-Euler theorem states that for integers $m\ge 1$ and $a$ with $\gcd (a,m)=1$,where Euler's totient function $\phi (m)$ counts the residue classes coprime to $m$. The case $m=1$ is trivial. For $m\ge 2$, list a reduced residue system $r_1,\dots ,r_{\phi (m)}$. Multiplication by $a$ permutes these classes: each $a{r}_i$ is coprime to $m$, and $a{r}_i\equiv a{r}_j$ implies $r_i\equiv r_j$ since $a$ has a multiplicative inverse modulo $m$. Multiplying the permuted residues givesThe product is itself coprime to $m$ and can be cancelled using its inverse, proving the theorem.

The integer 359 is prime: none of the primes $2,3,5,7,11,13,17$, all the primes not exceeding $\sqrt{359}<19$, divides it. Therefore $\phi (359)=358$ and 60 is coprime to 359. Using the supplied congruence and the Fermat-Euler theorem,Now express the decimal expansion by long division. Put $r_0=1$ and for $n\ge 1$ defineThus $r_n\equiv 10^n(\mathrm{mod}359)$, and none of these remainders is zero. The congruence $10^{179}\equiv 1$ implies $r_{n+179}\equiv r_n$; since both are the unique representatives between zero and 358, they are equal. A digit is determined by the preceding remainder, namely $a_n=\lfloor 10r_{n-1}/359\rfloor$, soThis proves the required pure periodicity from the first digit. In fact its least period is 179: the multiplicative order of 10 modulo 359 divides the prime 179 and is not one, since $10\not\equiv 1(\mathrm{mod}359)$. The connection between the remainder recurrence and the period is the decimal period from multiplicative order.