Proof of Fundamental Theorem of Arithmetic: Uniqueness Part of Proof

Question

I am having trouble trying to understand the uniqueness part of the proof. It uses induction on n (n is claimed to have a unique factorization of primes).

Here is my understanding so far:

Let $n$ be an integer such that $n>1$. Then $n=p_{1}p_{2}\cdots p_{k}$, with $p_{1},p_{2},...,p_{k}$ being primes, is a unique factorization of $n$.

Proof: (Uniqueness) (proof by induction) The base case states that for $n=2$, $n$ is a product of primes, which is true ($2$ is prime).

Now assume this is true for integers $m$ with $1\leq m < n$.

This is the part I don't understand. Why is $m \geq 1$ when $1$ cannot be written as a product of primes?

and $n=p_{1}p_{2}\cdots p_{k} = q_{1}q_{2}\cdots q_{l}$ with $p_{1}\leq p_{2}\leq \cdots \leq p_{k}$ and $q_{1}\leq q_{2}\leq \cdots \leq q_{l}$

Again, I am lost. Why is $n$ written in such a way when the inductive hypothesis uses $m$? Is it because the inductive step uses $n$ still and the fact for $m$ is used implicitly?

Then $p_{1} |q_{i}$ for some $1\leq i \leq l$ and $q_{1} |p_{j}$ for some $1\leq j \leq k$. Since all $p_{j}$ and $q_{i}$ are prime, their only divisors are $1$ and itself. Therefore, $p_{1} =q_{i}$ and $q_{1}=p_{j}$. Since $p_{1} \leq p_{j} = q_{1} \leq q_{i}=p_{1}$, $p_{1}=q_{1}$.

I understand this part of the proof.

Then by inductive hypothesis, $n'=p_{2}\cdots p_{k} = q_{2}\cdots q_{l}$.

Is this because, since $p_{1}=q_{1}$, they are cancelled out creating a new integer $n'$? And so does this induction continue until $p_{k}=q_{l}$, which will ultimately lead to $1=1$?

This proof by induction is very brief for me to understand and digest right away.

Answer 1

This is the part I don't understand. Why is $m\ge1$ when $1$ cannot be written as a product of primes?

In a technical sense, $1$ is a product of primes - it's the empty product (and the empty set $\varnothing$ is vacuously a set of primes, in the sense that it does not contain an element which is not prime), but you might as well just assume the author instead wrote $2\le m< n$ (except for the small caveat of how the proof functions when $n$ itself is prime).

Again, I am lost. Why is $n$ written in such a way when the inductive hypothesis uses $m$? Is it because the inductive step uses $n$ still and the fact for $m$ is used implicitly?

This is how induction always works: after you assume your base case ($2$) and your inductive hypothesis (all $m<n$), you then explore the claim for the value of $n$ itself. Here, we've assumed the claim (unique factorization) is true for all $m<n$, and now we're going to see if the claim holds as well for the number $n$.

So we write two factorizations for $n$, and show they must in fact be the same factorization (in such a way that will use the inductive hypothesis).

Is this because, since $p_1=q_1$, they are cancelled out creating a new integer n′n′?

Yes.

And so does this induction continue until $p_k=q_l$, which will ultimately lead to $1=1$?

Essentially, yes. Logically, this is a strong induction proof (which is why our inductive hypothesis involved all integers $m$ less than $n$, not just one), so we seem to be applying our inductive hypothesis to the value $m=n'$ in order to conclude the two factorizations of $n'$ are the same.