Past exam of the mathematics course of the University of Cambridge / 2007 / ia / Paper 4 / 8E / i / Solution

If the prime $p$ does not divide $x$, then $\gcd (p,x)=1$. The Bezout identity gives integers $a,b$ with $ap+bx=1$. Multiplying by $y$ gives $apy+bxy=y$. If $p\mid xy$, both terms on the left are divisible by $p$, so $p\mid y$. Thus Euclid lemma holds:For completeness, existence in the fundamental theorem of arithmetic follows by strong induction on a positive integer $n>1$. If $n$ is prime there is nothing to prove; otherwise $n=ab$ with $1<a,b<n$, and the inductive prime factorizations of $a,b$ give one for $n$. The integer $1$ has the empty factorization.

For uniqueness, suppose $p_1\cdots p_r=q_1\cdots q_s$ are two prime factorizations. Repeated application of Euclid lemma shows that $p_1$ divides some $q_j$. Both are primes, so they are equal. Reorder the second list, cancel this equal factor, and repeat. All factors must be matched, including their multiplicities. Thus prime factorization exists and is unique up to the order of its factors. For nonzero negative integers one also records the sign.