1.2 The Fundamental Theorem of Arithmetic

Multi

Lemma 1.2.1 (Euclid’s Lemma)

Let $m,n\in \mathbb{Z}$, and let $p$ be a prime dividing $mn$. Then $p$ divides $m$ or $n$.

Proof

Suppose $p\nmid m$. Then $\gcd (p,m)=1$, and Bezout’s Lemma furnishes integers $x$ and $y$ such that
$mx+py=1$
Now, $n=n(mx+py)$ is divisible by $p$. It is necessary to assume that $p$ is prime.

Theorem 1.2.2 (Fundamental Theorem of Arithmetic)

Proof

Let $n\in \mathbb{N}$. We prove existence by strong induction. For $n=1$, we use the empty product. For $n>1$m we may assume that $n$ is composite, so $n=ab$ for some integers $a,b\in (1<a,b<n)$. By out inductive hypothesis, the integers $a$ and $b$ are the product of primes. Thus, so is $n$.
For uniqueness, we also use strong induction. If $n=1$ is expressed as a product of primes, then it must be the empty product, since any other product of primes is at least 2. Now suppose
$2\le n=p_1...p_s=q_1...q_t$
for some primes $p_1,...,p_s$ and $q_1,...,q_t$. By Euclid’s Lemma (left), the prime $p_1$ must divide some $q_j$, and therefore must equal $q_j$. By reordering the primes $q_j$, we may assume that $p_1=q_1$. Now
$p_2...p_2=q_2...q_t<n$
So by our inductive hypothesis we must have the multiset equality
$\{\{p_2,...,p_s\}\}=\{\{q_2,...,q_t\}\}$.
Finally, as $p_1=q_1$, we have
$\{\{p_1,...,p_s\}\}=\{\{q_1,...,q_t\}\}$

Notation The least common multiple of $x,y\in \mathbb{Z}$, denoted $\text{lcm}(x,y)$ or $[x,y]$, is the least positive integers that is a multiple of both $x$ and $y$.

Lemma 1.2.3

Let $x,y\in \mathbb{N}$. Let $p_1,...,p_k$ be the distinct primes dividing $xy$, and let
$x=p_1^{a_1}...p_k^{a_k},y=p_1^{b_1}...p_k^{b_k}$
be the prime factorisations of $x$ and $y$ respectively. Then
$(x,y)={\prod }_{i\le k}{p}_i^{m_1},[x,y]={\prod }_{i\le k}{p}_i^{M_i},$
where $m_i=\min (a_i,b_i)$ and $M_i=\max (a_i,b_i)$

Proof

todo

Corollary 1.2.4

if $x,y\in \mathbb{N}$ then
$(x,y)[x,y]=xy$

Two (or more) integers are coprime or (relatively prime) if they don’t have any prime factors in common. By Bezout’s Lemma, this happens if and only if 1 can be expressed as a linear combination of the two integers. The following two lemmas can be proved using either this characterisation or the fundamental theorem of arithmetic.

Multi

Lemma 1.2.5

If $(a,m)=(b,m)=1$ then $(ab,m)=1$

Lemma 1.2.6 (General Euclid Lemma)

If $d\mid xy$ and $(d,x)=1$ then $d\mid y$

Example 1.2.7

Unique factorisation into irreducible elements fails in the ring $\mathbb{Z}[\sqrt{-5}]$, since
$(1+\sqrt{-5})(1-\sqrt{-5})=2\times 3$