Reformulation of Fundamental Theorem of Arithmetic

Question

My book claims the following.

The fact that for coprime numbers $a$ and $b$ there exists integers $x$ and $y$ such that $ax-by=1$ is called the fundamental theorem of arithmetic.

Obviously, this is not the standard statement of the fundamental theorem of arithmetic (which instead talks about the uniqueness of prime factorization). My question is: how are the two formulations the same?

I at least understand one direction: if two numbers are coprime, then their greatest common divisor is $1$, so the existence of $x$ and $y$ follows from Bézout's lemma. But why is it true that the existence of the integers $x$ and $y$ for coprime $a$ and $b$ implies unique prime factorization?

Answer 1

The property that for elements $a$ and $b$ with greatest common divisor, $d$, there exists elements $x$ and $y$ such that $ax + by = d$ is called Bézout's identity. Integral domains with this property are called Bézout domains. An integral domain in which every element can be written in an essentially unique way as a product of primes is called a unique factorization domain (or UFD). The ring $\Bbb{Z}$ of integers has both these properties, so in a trivial sense, these properties are equivalent (in $\Bbb{Z}$), because they are both true. It is the fact that $\Bbb{Z}$ is a UFD that is known (by everyone, AFAIK, except the authors of this book) as the fundamental theorem of arithmetic.

The Wikipedia article on Bézout domains gives several examples of Bézout domains that are not UFDs, so Bézout's identity is not equivalent to the statement of the fundamental theorem of arithmetic for integral domains in general. Let me sketch one of the simplest examples. Let $\Bbb{Q}[x]$ be the ring of polynomials in one variable $x$ over the rational numbers $\Bbb{Q}$. Define a subring $R$ of $\Bbb{Q}[x]$ by: $$ R = \{ f \in \Bbb{Q}[x] \mid f(0) \in \Bbb{Z}\} $$ So $R$ comprises polynomials $c_0 + c_1x + c_2x^2 + \ldots + c_nx^n$ where all the $c_i$ are rational and $c_0$ is an integer. $R$ is easily checked to be a subring of $\Bbb{Q}[x]$, and, hence as a subring of an integral domain, it, too, is an integral domain. $R$ is not a UFD, since the polynomial $x$ can be divided infinitely often by the constant polynomial $2$, which is a prime in $R$: $$ x = 2\frac{x}{2} = 2^2\frac{x}{4} = \ldots = 2^n\frac{x}{2^n} = \ldots $$ However $R$ can be shown to be a Bézout domain (this is done by reducing to the case when both $a$ and $b$ have non-zero constant terms and then using the fact that $\Bbb{Q}[x]$ is a Bézout domain).

Answer 2

(1.) If $a,b$ are co-prime and $a|bc$ then $a|c.$ Proof: Take integers $x,y$ with $ax+by=1.$ Then $c/a=(ax+by)c/a=xc+(bc/a)y\in\Bbb Z$ because $(bc/a)\in\Bbb Z.$

(2.) For prime $p$ and for a list $q_1,...,q_n$ of (not necessarily distinct) primes, if $p|\prod_{i=1}^nq_i$ then $p$ is equal to one of $q_1,...,q_n.$

Proof by induction on $n$: The case $n=1$ is obvious. Suppose case $n$ is true. For prime $p$ and primes $q_1,...,q_{n+1}$ with $p|\prod_{i=1}^{n+1}q_i$, let $p=a$ and $b=q_{m+1}$ and $c=\prod_{i=1}^nq_i.$ Either (i) $p=q_{m+1}$ or (ii) $p$ is co-prime to $q_{n+1},$ which by (1.) implies $p=a|c=\prod_{i=1}^mq_i,$ which by case $n$ implies $p$ is one of $q_1,...,q_n.$

(3.) Let $(p_1,...,p_m)$ and $(q_1,...,q_n)$ be lists of primes, each list being in increasing order. That is, $p_i\le p_{i+1}$ and $q_j\le q_{j+1}.$ If $\prod_{i=1}^{m}p_i=\prod_{j=1}^nq_j $ then the two lists are the $same$ list.

Proof by induction on $m$: The case $m=1$ is obvious. Suppose case $m$ is true and suppose $(p_1,...,p_{m+1}),(q_1,...,q_n)$ are lists of primes, each in increasing order, and $\prod_{i=1}^{m+1}p_i=\prod_{j=1}^nq_j.$

By (2.) we have $p_{m+1}=q_{j_0}$ for some $j_0$ because $p_{m+1}|\prod_{j=1}^{n}q_j.$ Also by (2.) we have $q_n=p_{i_0}$ for some $i_0$ because $q_n|\prod_{i=1}^{m+1}p_i.$ Hence $p_{m+1}=q_{j_0}\le q_n=p_{i_0}\le p_{m+1},$ implying $p_{m+1} =q_n.$

So $\prod_{i=1}^mp_i=\prod_{j=1}^{n-1}q_j$.

Now case $m$ implies that $(p_1,...,p_m)$ and $(q_1,...,q_{n-1})$ are the same list. And we have $p_{m+1} =q_n.$ So $(p_1,...,p_{m+1})$ and $(q_1,...,q_n)$ are the same list.