\input fremtex
%\fullsize
\smallprint
\def\ufd{unique factorisation domain}
\def\Ed{Euclidean domain}
\def\pid{principal ideal domain}
\def\id{integral domain}
\def\gcd{greatest common divisor}
\filename{rfch4.tex}
\versiondate{9.6.03}
\Centerline{\bf Rings and Fields}
\noindent{\bf 4. Unique Factorisation Domains}
\medskip
{\bf 4A Associates} Let $R$ be an integral domain.
\medskip
{\bf (a)} If $a$, $b\in R$, then $b$ is an {\bf associate} of $a$ if
there is an invertible element $e$ of $R$ such that $b=ea$.
\medskip
{\bf (b)(i)} If $a\in R$ then $a=1a$ so $a$ is an associate of itself.
{\bf (ii)} If $a$ is an associate of $b$, there is an invertible $e$
such that $a=be$; now $e^{-1}$ is invertible and $b=e^{-1}a$ so $b$ is
an associate of $a$. {\bf (iii)} If $a$ is an associate of $b$ and $b$
is an associate of $c$, there are invertible $e$, $e'$ such that $a=eb$
and $b=e'c$; now $ee'$ is invertible and $a=ee'c$ so $a$ is an
associate of $c$.
Thus \lq is an associate of' is an equivalence relation.
\medskip
{\bf (c)(i)} The only associate of $0$ is $0$ itself.
\quad{\bf (ii)} The associates of $1$ are the invertible elements of
$R$.
\quad{\bf (iii)} If $p\in R$ is irreducible, then every associate of $p$
is irreducible. \Prf\ Suppose that $q$ is an associate of $p$. Then
$q$ is
non-zero and non-invertible because $p$ is (using (i)-(ii) just above).
If $q=ab$, let $e$ be an invertible element of $R$ such that $p=eq$;
then $p=(ea)b$. Because $p$ is irreducible, one of $ea$, $b$ must be
invertible. If $ea$ is invertible, so is $a=e^{-1}(ea)$; so one of
$a$, $b$ must be invertible. As $a$, $b$ are arbitrary, $q$ is
irreducible. \Qed
\quad{\bf (iv)} If $p\in R$ is prime, then every associate of $p$ is
prime. \Prf\ Suppose that $q$ is an associate of $p$. Then $q$ is
non-zero and non-invertible. Now suppose that $qr=ab$. Let $e\in R$
be an invertible element such that $q=pe$; then $per=ab$, so $ab$ is a
multiple of $p$ and one of $a$, $b$ is a multiple of $p$. If $a$ is a
multiple of $p=e^{-1}q$, then $a$ is a multiple of $q$; if $b$ is a
multiple of $p$ then $b$ is a multiple of $q$. \Qed
\medskip
{\bf (d)(i)}
If $a$, $b\in R$ then $a$ and $b$ are associates iff each is a multiple
of other. (If $a=0$ this is trivial. If $a\ne 0$ and $a=be$, $b=ae'$
then $a=aee'$ so $ee'=1$ and $e$ is invertible.)
{\bf (ii)} If $a$, $b\in R$ then $a$ and $b$ are associates iff they
have the same multiples in $R$. {\bf (iii)} If $a$, $b\in R$ then $a$
and $b$ are associates iff they have the same factors in $R$.
\medskip
{\bf (e) Examples (i)} In $\Bbb Z$, the associates of any $n\in\Bbb Z$
are $\pm n$. {\bf (ii)} In $\Bbb Q[x]$, the associates of any
polynomial are the
non-zero constant multiples of that polynomial.
\medskip
{\bf 4B Definition} A {\bf unique factorisation domain} is an integral
domain $R$ such that for every
non-zero, non-invertible $a\in R$
(i) there are irreducible elements $p_1,\ldots,p_n\in R$ such that
$a=p_1\ldots p_n$ (allowing $n=1$ if $a$ itself is irreducible);
(ii) if $q_1,\ldots,q_m$ are further irreducible elements of $R$ such
that $a=q_1\ldots q_m$ then $m=n$ and the $q_k$ can be
re-ordered in such a way as to make each $q_k$ an associate of $p_k$.
\medskip
\noindent{\bf Example} In $\Bbb Z$, we can express $60$ as a product of
irreducibles in various ways; for instance, $60=2.2.3.5=
3.(-2).(-5).2$. But all such expressions have four factors and in all
such expressions the factors are $\pm 2$, $\pm 2$, $\pm 3$, $\pm 5$ in
some order.
\medskip
{\bf 4C Proposition} Let $R$ be an integral domain. Then the following
are equivalent:
(i) $R$ is a unique factorisation domain;
(ii) Irreducible elements of $R$ are prime and every
non-zero, non-invertible element of $R$ is expressible as a product of
irreducible elements.
\medskip
\noindent{\bf proof (a)(i)$\Rightarrow$(ii)}
Suppose that $R$ is a unique factorisation domain. Then of course
every
non-zero,
non-invertible
element is expressible as a product of irreducibles. To see that
irreducibles
are prime, let $p$ be irreducible, and suppose that $p$ is a factor of
$ab$;
that $pc=ab$. If either $a$ or $b$ is $0$, then it is a multiple of
$p$; if
either $a$ or $b$ is invertible then the other is a multiple of $p$.
If
none of these happen, then $ab\ne 0$ (because $R$ is an integral domain)
so
$c\ne 0$; also, because $p$ is irreducible, it cannot be a multiple of
$ab$,
so $c$ is not invertible.
We may therefore express $a$, $b$, $c$ as products of irreducibles,
\centerline{$a=q_1\ldots q_k$, $b=q'_1\ldots q'_m$, $c=p_1\ldots p_n$}
\noindent and get $pp_1\ldots p_n=q_1\ldots q_kq'_1\ldots q'_m$.
Because
factorisation in $R$ is unique, we must have $k+m=1+n$ and also $p$ must
be an associate of one of the $q_i$ or $q_j'$.
But in
this
case, because every $q_i$ is a factor of $a$ and every $q'_j$ is a factor
of
$b$, $p$ is a factor of at least one of $a$, $b$. As $a$ and $b$ are
arbitrary, $p$ is prime, as required.
\medskip
{\bf (b)(ii)$\Rightarrow$(i)}
Now suppose that $R$ satisfies the two conditions. To show that $R$ is
a
unique factorisation domain we need to
prove (ii) of 4C.
Do this by induction on $n$.
If
$n=1$ we have $p_1=q_1\ldots q_m$; but as $p_1$ is irreducible all but
one
of the $q_i$ must be invertible, and this means that $m=1$ and $q_1=p_1$
is an associate of $p_1$. For the inductive step to
$n+1$ we have $p_1\ldots p_np_{n+1}=q_1\ldots q_m$. Now this means
that
$p_{n+1}$ is a factor of $q_1\ldots q_m$; but $p_{n+1}$ is irreducible
and
we are supposing that irreducibles are prime, so $p_{n+1}$ is a factor
of
$q_k$ for some $k\le m$. Since
$q_k$ is also irreducible, there must be an invertible $e$ such that
$q_k=ep_{n+1}$. Now we have
\centerline{$p_1\ldots p_n=eq_1\ldots q_{k-1}q_{k+1}\ldots q_m$}
\noindent (because $R$ is an integral domain, so we may cancel $p_{n+1}$
from both sides). But $eq_1$ (or $eq_2$, if $k=1$) is also
irreducible (4A(c-iii)), so the inductive hypothesis
tells us that $n=m-1$ and that $eq_1,\ldots,q_{k-1},q_{k+1},\ldots,q_m$
can be got by shuffling $p_1,\ldots,p_n$ and multiplying them by
appropriate
invertible elements. But this means that $n=m+1$ and (since
$q_k=ep_{n+1}$)
the whole list $q_1,\ldots,q_m$ can be got by shuffling
$p_1,\ldots,p_{n+1}$
and multiplying them by invertible elements. Thus the induction
proceeds.
\medskip
{\bf 4D Theorem} (a) Every principal ideal domain is a unique
factorisation domain.
(b) Every Euclidean domain is a unique factorisation domain.
\medskip
\noindent{\bf proof (a)} Let $R$ be a principal ideal domain. In
3\query we saw that irreducibles in $R$ are prime; in 3\query we saw
that every
non-zero, non-invertible element of $R$ is a product of irreducibles.
And of course $R$ is an integral domain. So 4C tells us that $R$ is a
unique factorisation domain.
\medskip
{\bf (b)} By 3\query every Euclidean domain is a principal ideal domain;
by (a), it is also a unique factorisation domain.
\medskip
{\bf 4E Greatest common divisors} Let $R$ be a unique factorisation
domain.
If $a_1,\ldots,a_n$ are
non-zero elements of $R$,
a {\bf greatest common divisor} of $a_1,\ldots,a_n$ is a $c\in R$ such
that (i) $c$ is a factor of every $a_k$ (that is, every $a_k$ is a
multiple of $c$ (ii) if $d$ is any other common divisor of
$a_1,\ldots,a_n$ then $c$ is a multiple of $d$.
\medskip
{\bf 4F Lemma} Let $R$ be a unique factorisation domain.
(a) If $c$ is a \gcd\ of $a_1,\ldots,a_n\in R\setminus\{0\}$ and $b\in
R\setminus\{0\}$, then $bc$ is a \gcd\ of $ba_1,\ldots,ba_n$.
{(b)} If $a_1,\ldots,a_n\in R\setminus\{0\}$, where $n\ge 1$, then they
have a greatest common divisor.
(c) If $c$ is a \gcd\ of $a_1,\ldots,a_n\in R\setminus\{0\}$, then there
are $a_1',\ldots,a_n'$ such that $a_k=ca_k'$ for each $k\le n$, and now
$1$ is a \gcd\ of $a_1',\ldots,a'_n$.
\medskip
\noindent{\bf proof} Define $\nu:R\setminus\{0\}\to\Bbb N\cup[\{0\}$ by
writing $\nu(a)=0$ if $a$ is invertible, and $\nu(a)=m$ if $a=p_1\ldots
p_m$ where $p_1,\ldots,p_m$ are irreducible; because $R$ is a \ufd,
$\nu$ is
well-defined.
\medskip
{\bf (a)} I show by induction on $m$ that if $\nu(b)=m$ then $bc$ is a
\gcd\ of $ba_1,\ldots,ba_n$.
The induction starts with $m=0$, in which case $b$ is invertible, so
that the factors of $ba_k$ are precisely the factors of $a_k$, for each
$k$, and the common divisors of $ba_1,\ldots,ba_n$ are just the common
divisors of $a_1,\ldots,a_k$; accordingly $c$ and $bc$ are
\gcd s of $ba_1,\ldots,ba_n$.
Next, if $m=1$, then $b$ is irreducible, therefore prime. Of course
$bc$ is a factor of $ba_k$ for every $k$. Now suppose that $d$ is a
common divisor of $ba_1,\ldots,ba_n$. If $d$ is a multiple of $b$, say
$d=bd'$, then $ba_k$ is a multiple of $bd'$, so $a_k$ is a multiple of
$d'$, for every $k$; accordingly $d'$ is a common divisor of the $a_k$,
and must be a factor of $c$, so that $d=bd'$ is a factor of $bc$. If
$d$ is invertible, then of course it is a factor of $bc$. If $d$ is
not a multiple of $b$, then for each $k$ we can express $ba_k$ as
$da_k'$. Now $da_k'$ is a multiple of $b$, but $d$ is not, so $a_k'$
is a multiple of $b$; say $a_k'=ba_k"$, $ba_k=bda_k"$. Cancelling
$b$, we have $a_k=da_k"$. But this is true for each $k$, so $d$ is a
common divisor of $a_1,\ldots, a_k$ and is a factor of $c$, therefore of
$bc$. Thus in any case $d$ is a factor of $bc$ and $bc$ is a \gcd\ of
$a_1,\ldots,a_n$.
Now, for the inductive step to $m>1$, if $\nu(b)=m$ then we can express
$b$ as $pb'$ where $\nu(b')=m-1$. By the inductive hypothesis, $b'c$
is a \gcd\ of $b'a_1,\ldots,b'a_n$. By the case $m=1$, $pb'c$ is a
\gcd\ of $pb'a_1,\ldots,pb'a_n$; that is, $bc$ is a \gcd\ of
$ba_1,\ldots,ba_n$, and the induction continues.
\medskip
{\bf (b)} Now I show by induction on $\nu(a_1)$ that if
$a_1,\ldots,a_n\in R\setminus\{0\}$ then $a_1,\ldots,a_n$ have a \gcd.
The induction starts with the case $\nu(a_1)=0$; in this case $a_1$ is
invertible, so all its factors are invertible, and $1$ is a \gcd\ of
$a_1,\ldots,a_n$. For the inductive step to $\nu(a_1)=m>0$, if $1$ is
a \gcd\ of $a_1,\ldots,a_n$ we can stop. Otherwise, they have a
non-invertible \gcd, which has an irreducible factor; so there is an
irreducible $p\in R$ which is a common factor of $a_1,\ldots,a_n$.
Express $a_k$ as $pa_k'$ for each $k$. Then $\nu(a_1')=m-1$ so by the
inductive hypothesis $a_1',\ldots,a_n'$ have a \gcd\ $c'$ say. Now by
(a) of this proposition, $pc'$ is a \gcd\ of $a_1,\ldots,a_n$.
Thus the induction continues.
\medskip
{\bf (c)} Because $c$ is a factor of $a_k$, we can find for each $k\le
n$ an $a'_k$ such that $a_k=ca'_k$. By (b), $a'_1,\ldots,a'_k$ have a
\gcd\ $c'$ say, and now $cc'$ is a \gcd\ of $a_1,\ldots,a_k$, by (a);
but this means that $c$ is a multiple of $cc'$, say $c=cc'd$, and
$c'd=1$, so that $c'$ is invertible. Consequently all common divisors
of $a_1',\ldots,a_n'$ are invertible and $1$ is a \gcd\ of
$a_1',\ldots,a_n'$, as claimed.
\medskip
{\bf 4G Primitive polynomials} Let $R$ be a \ufd. A
non-zero polynomial $f\in R[x]$ is {\bf primitive} if $1$ is a \gcd\ of
its
non-zero coefficients.
If $f\in R[x]$ is any
non-zero polynomial, let $c$ be a \gcd\ of its
non-zero coefficients; then $f$ can be expressed as $cg$ where $g$ is
primitive (using 4Fc).
\medskip
{\bf 4H Proposition} Let $R$ be a \ufd. If $f$ and $g$ are primitive
polynomials in $R[x]$, then $f\times g$ is still primitive.
\medskip
\noindent{\bf proof} \Quer\ Suppose, if possible, otherwise; that the
non-zero coefficients of $f\times g$ have a
non-invertible common divisor. Then they have an irreducible common
divisor $p$ say, which is prime. Suppose $f=\sum_{i=0}^ma_ix^i$,
$g=\sum_{i=0}^nb_ix^i$. There must be $j\le m$, $k\le n$ such that $p$
is not a factor of $a_j$ nor of $b_k$; take the least such. Now
examine the coefficient $c$ of $x^{j+k}$ in $f\times g$.
This is supposed to be a multiple of $p$. But also we have
\centerline{$c
=a_0b_{j+k}+a_1b_{j+k-1}+\ldots+a_jb_k+\ldots+a_{j+k}b_0$.}
\noindent So
\centerline{$a_jb_k=
c-a_0b_{j+k}-\ldots-a_{j-1}b_{k+1}-a_{j+1}b_{k-1}
-\ldots-a_{j+k}b_0$.}
\noindent All the terms on the right are multiples of $p$ (because $a_i$
is a multiple of $p$ if $i1$, \Quer\ suppose, if possible, otherwise.
Let $d$ be the greatest common divisor of $a$, $b$ in $\Bbb N$. Then
$d^4$ is a factor of $c^2$ so $d^2$ is a factor of $c$. Express $a$ as
$da_1$, $b$ as $db_1$, $c$ as $d^2c_1$; then $a_1^4+b_1^4=c_1^2$, and
$a_1$, $b_1$ are coprime. By the inductive
hypothesis, $c_1\ge c$, so in fact $c_1=c$ and $d=1$ and $a$, $b$ are
coprime.
By 6H, there are $p$, $q\in\Bbb Z$ such that one of $a^2$, $b^2$ is
$2pq$ and the other is
$p^2-q^2$; thus $2pq$ and
$p^2-q^2$ are both
perfect squares, while $p$ and $q$ are still coprime. Note that
$p^2-q^2$ must be odd, and that $c=p^2+q^2$. Without loss of
generality, we may take it that
$b^2=p^2-q^2$, so that $b^2+q^2=p^2$.
Once again, because $a^2=2pq$, $b$ and $q$ are coprime, so there are
coprime $p_1$, $q_1$ such that $q=2p_1q_1$ and
$b=p_1^2-q_1^2$ (note
that $b$ must be odd).
Now $a^2=2pq=4pp_1q_1$ so $pp_1q_1$ is a perfect square; because $p$
and $p_1q_1={1\over 2}q$ are coprime, $p$ and $p_1q_1$ are perfect
squares. Because $p_1$ and $q_1$ are coprime, they also are perfect
squares. But now, if $p=\tilde c^2$, $p_1=\tilde a^2$, $q_1=\tilde
b^2$ we have $\tilde a^4+\tilde b^4=\tilde c^2$, while $\tilde a$,
$\tilde b$ are both
non-zero.
By the inductive hypothesis, $\tilde c\ge c$. But this is absurd,
because $c=p^2+q^2$, so $\tilde c^2=p