fundamental theorem of arithmetic — Jemoka Knowledge Base

\begin{equation} \gcd (a,p) = 1 = s a + tp \end{equation}

We note that:

\begin{align} b &= 1 \cdot b \\ &= (sa+tp) b \\ &= sab + tpb \\ &= 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’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’t empty. By WOP, take some smallest element of t \in T. t is not in S, so it mustn’t be prime. This means:

\begin{equation} t = ab \end{equation}

Though…. a and b must be smaller than t (otherwise their product wouldn’t make t, as we are working with only positive numbers (integers greater than 1) here). So a and b must be in S—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 … \leq p_{r}, q_1 \leq … \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 … 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 — 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} < n. Now, we can invoke induction. \blacksquare