Past exam of the mathematics course of the University of Cambridge / 2011 / ia / Paper 4 / 5E / a / Solution

The greatest common divisor $d=\gcd (a,b)$ is the largest positive integer dividing both $a$ and $b$. To prove Bezout identity without assuming unique factorization, let $d_0$ be the least positive member ofThis set has positive members, for example $a$, so well-ordering principle supplies $d_0$. Divide $a$ by $d_0$ using Euclidean division: $a=q{d}_0+r$, $0\le r<d_0$. The remainder $r=a-q{d}_0$ is another integer linear combination of $a,b$. Minimality forces $r=0$, so $d_0\mid a$. The same argument gives $d_0\mid b$. Every common divisor divides every integer linear combination, hence divides $d_0$. Therefore $d_0$ is the greatest common divisor, andThis argument also proves that every common divisor divides the greatest common divisor.

The positive integers with the stated product-divisibility property areThe case $n=1$ is immediate. If $p$ is prime and $p\nmid a$, its only possible common positive divisor with $a$ is one. By Bezout identity, $\lambda p+\mu a=1$. Multiplying by $b$ shows that $p\mid ab$ implies $p\mid b$. This proves Euclid lemma directly. Conversely, if $n>1$ is not prime, it has a divisor $r$ with $1<r<n$. Put $s=n/r$; then $1<s<n$. Although $n\mid rs$, neither $r$ nor $s$ is divisible by $n$, disproving the property for a composite $n$.

Finally, suppose $ab=cd$ for four distinct primes. Then $a\mid cd$, so Euclid lemma gives $a\mid c$ or $a\mid d$. A prime has no positive divisor other than one and itself, so this would mean $a=c$ or $a=d$, a contradiction. Products of these two disjoint pairs cannot be equal. No form of the fundamental theorem of arithmetic was used: the required prime-divisibility fact was proved from Bezout identity.