Past exam of the mathematics course of the University of Cambridge / 2011 / ia / Paper 4 / 5E (Numbers and Sets)

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.

Yes. A concrete example of nonunique factorization in a congruence submonoid isThe four factors are distinct and each is congruent to one modulo ten. The primes $3,7,13,17$ can be checked by trial division by two and three. Their elementary prime decompositions areFor any one of these products $pq$, where $p,q$ are the indicated distinct primes, its positive divisors are $1,p,q,pq$. This divisor assertion does not require unique factorization: if $d\mid pq$ and $p\nmid d$, then $p\mid pq/d$ by the Euclid lemma proved in (a), so $d\mid q$ and $d$ is either one or $q$. If $p\mid d$, write $d=pe$ and obtain $e\mid q$, giving $d=p$ or $pq$.

None of $3,7,13,17$ is congruent to one modulo ten. Consequently no listed product has a proper nonunit divisor in $S$. Thus each is an irreducible element of a commutative monoid, and the displayed equality proves the claim. Ordinary prime decompositions and irreducibility relative to the smaller commutative monoid $S$ are different notions.