Suggest edit — fundamental theorem of arithmetic

Title

Name

Note

---
title: "fundamental theorem of arithmetic"
type: concept
related: [Divide, Integer, Prime]
source: https://www.jemoka.com/posts/kbhfundamental_theorem_of_arithmetic/
confidence: high
status: active
---

factorization motivator If $p$ is prime and $p | ab$, then $p|a$ or $p|b$.
If $p|a$, we are done.
Consider the case where $p|ab$ yet $a$ is not divisible by $p$. Then, $a$ and $p$ are coprime. This means that, we have:
\begin{equation} \gcd (a,p) = 1 = s a + tp \end{equation}
We note that:
\begin{align} b &amp;= 1 \cdot b \\ &amp;= (sa+tp) b \\ &amp;= sab + tpb \\ &amp;= s(ab) + tb(p) \end{align}
Notice that both of these elements are divisible by $p$ ($p|ab$ and of course $p|p$). Therefore, $p|b$ as desired.
statement of the theorem Every integer greater than $1$ is a prime or a product of primes. This factorization is unique.
Proof Existence Let $S$ be the list of integers bigger than $1$ which are prime or are products of primes. Consider the set $T$ which is all integers bigger than $1$ which isn&rsquo;t prime or are products of primes:
\begin{equation} T = \{2, 3, \dots, \} \setminus S \end{equation}
We desire $T$ to be empty.
Assume for the sake of contradiction that $T$ isn&rsquo;t empty. By WOP, take some smallest element of $t \in T$.
$t$ is not in $S$, so it mustn&rsquo;t be prime. This means:
\begin{equation} t = ab \end{equation}
Though&hellip;. $a$ and $b$ must be smaller than $t$ (otherwise their product wouldn&rsquo;t make $t$, as we are working with only positive numbers (integers greater than $1$) here). So $a$ and $b$ must be in $S$&mdash;meaning they are primes or product of primes. This makes $t$ a prime or product of primes, reaching contradiction.
Uniqueness We show this by induction. We see that: $2 = 2$. Now, suppose a unique prime factorization holds for all integers smaller than $n$. Let:
\begin{equation} n = p_1 \dots p_{r} = q_1 \dots q_{s} \end{equation}
Let us order it such that $p_1 \leq &hellip; \leq p_{r}$, $q_1 \leq &hellip; \leq q_{s}$.
By the factorization motivator, each $p_{j}|n$ implies that $p_{j}|q_{i}$ (you can see this by treating $n = q_1 &hellip; q_{s}$, so $p_{j}|n \implies p_{j}|(q_1 \cdot \dots \cdot q_{s})$ so $p_{j}$ should be divisible by some $q_{j}$.)
Now, this condition implies $p_{j} = q_{i}$, because primes are not divisible by anything except themselves and $1$ (and $1$ is not considered prime).
Consider, then, two such equivalences:
\begin{equation} p_{1} = q_{j} \end{equation}
\begin{equation} q_{1} = p_{k} \end{equation}
Now, this means that:
\begin{equation} p_{1} \leq p_{k} = q_{1} \leq q_{j} = p_{1} \end{equation}
Therefore, the only way this can work (the fact that $q_1$ is sandwiched on both ends &mdash; by $p_1\leq q_1 \leq p_1$) is that $p_1 = q_1$.
Therefore, we now have:
\begin{equation} \frac{n}{p_1} = p_{2} \cdot \dots \cdot p_{n} = q_{2} \cdot \dots \cdot q_{n} \end{equation}
You will note $\frac{n}{p_1} &lt; n$. Now, we can invoke induction. $\blacksquare$