Past exam of the mathematics course of the University of Cambridge / 2007 / ia / Paper 5 / 12 (Numbers and Sets)

Suppose $p$ is a prime number, $p\mid xy$ and $p\nmid x$. Since the only positive divisors of $p$ are one and $p$, the greatest common divisor of $p$ and $x$ is one. By Bézout's identity, integers $u,v$ exist with $up+vx=1$. Multiplying by $y$ gives $upy+vxy=y$. Both terms on the left are divisible by $p$, so $p\mid y$. Thus Euclid lemma givesThe fundamental theorem of arithmetic says that every positive integer greater than one is a product of prime numbers, uniquely up to their order. Existence follows by strong mathematical induction: if $n$ is prime it already has a factorization; otherwise $n=ab$ with $1<a,b<n$, and the factorizations of $a,b$ combine to factor $n$.

For uniqueness, suppose $p_1\cdots p_r=q_1\cdots q_s$ are two prime factorizations. Repeated application of Euclid lemma makes $p_1$ divide one of the $q_j$, so primality forces $p_1=q_j$. Reorder that factor to the front, cancel it and repeat. Neither side can retain extra primes when the other has become one, since every prime exceeds one. The two multisets are therefore identical. For a negative integer there is additionally the uniquely determined sign; one has the empty positive factorization, and zero is excluded. The prime-product divisibility lemma is the step which makes factorization unique.

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.