Paper 4, Section II, E

Numbers and Sets | Part IA, 2007

(i) Let pp be a prime number, and let xx and yy be integers such that pp divides xyx y. Show that at least one of xx and yy is divisible by pp. Explain how this enables one to prove the Fundamental Theorem of Arithmetic.

[Standard properties of highest common factors may be assumed without proof.]

(ii) State and prove the Fermat-Euler Theorem.

Let 1/3591 / 359 have decimal expansion 0a1a20 \cdot a_{1} a_{2} \ldots with an{0,1,,9}a_{n} \in\{0,1, \ldots, 9\}. Use the fact that 60210(mod359)60^{2} \equiv 10(\bmod 359) to show that, for every n,an=an+179n, a_{n}=a_{n+179}.

Typos? Please submit corrections to this page on GitHub.