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

Which positive integers $n$ have the property that, for any positive integers $a$ and $b$, if $n$ divides $a b$ then $n$ divides $a$ or $n$ divides $b$ ? Justify your answer.

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

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

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