Paper 4, Section II, E

Numbers and Sets | Part IA, 2011

(a) What is the highest common factor of two positive integers aa and bb ? Show that the highest common factor may always be expressed in the form λa+μb\lambda a+\mu b, where λ\lambda and μ\mu are integers.

Which positive integers nn have the property that, for any positive integers aa and bb, if nn divides aba b then nn divides aa or nn divides bb ? Justify your answer.

Let a,b,c,da, b, c, d be distinct prime numbers. Explain carefully why aba b cannot equal cdc d.

[No form of the Fundamental Theorem of Arithmetic may be assumed without proof.]

(b) Now let SS be the set of positive integers that are congruent to 1 mod 10 . We say that xSx \in S is irreducible if x>1x>1 and whenever a,bSa, b \in S satisfy ab=xa b=x then a=1a=1 or b=1b=1. Do there exist distinct irreducibles a,b,c,da, b, c, d with ab=cd?a b=c d ?

Typos? Please submit corrections to this page on GitHub.