4
$\begingroup$

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?

$\endgroup$
9
  • 1
    $\begingroup$ i don't know if it's what's meant, but: it implies Euclid's Lemma (that $p|ab$ and $p\not |a$ implies $p|b$) from which uniqueness follows $\endgroup$
    – tomos
    Commented Sep 9, 2021 at 20:37
  • 1
    $\begingroup$ This article on Bezout domains, gives a construction of an integral domain which is not a UFD but does satisfy Bezout's lemma. (@tomos: I think you also need the integral domain to be Noetherian to deduce uniqueness.) $\endgroup$
    – Rob Arthan
    Commented Sep 9, 2021 at 20:46
  • 1
    $\begingroup$ @tomos: aside on LaTex/MathJax: "\not\mid" ($\not\mid$) gives a better result than "\not|" ($\not|$) $\endgroup$
    – Rob Arthan
    Commented Sep 10, 2021 at 22:02
  • 2
    $\begingroup$ In case, it wasn't clear from my comment, the statement that your book claims to be the fundamental theorem of arithmetic is not the fundamental theorem of arithmetic: the two formulations are not the same. I can write up a more detailed answer, if you like. Please give a reference to the book. $\endgroup$
    – Rob Arthan
    Commented Sep 10, 2021 at 22:07
  • 1
    $\begingroup$ @RobArthan I would appreciate a detailed write up. The book that makes this claim is Putnam and Beyond. You can find it here on page 253: cms.zju.edu.cn/UploadFiles/AttachFiles/201082333637670.pdf $\endgroup$ Commented Sep 11, 2021 at 2:54

2 Answers 2

3
$\begingroup$

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).

$\endgroup$
1
  • $\begingroup$ @BarryCipra: no. Fixed. Thanks. $\endgroup$
    – Rob Arthan
    Commented Sep 12, 2021 at 17:02
1
$\begingroup$

(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.

$\endgroup$
1
  • 1
    $\begingroup$ You haven't made it clear how your argument relates to the question. I think you have proved that prime factorisations are unique (ish) when they exist. You have not proved that they always exist. Bézout's identity alone will not give you the existence without using properties of the integers that do not hold in all Bézout domains. $\endgroup$
    – Rob Arthan
    Commented Sep 13, 2021 at 22:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .