Factor of a product is product of factors

Question

I'm trying to prove the uniqueness of prime factorization of any natural number $n\ge 2$ (I take $0\in\mathbb N$). I've shown the existence of a prime factorization for any such number (by infinite descent on the statement that 'for each $n\ge 2$, there exists a greatest prime that divides $n$').

To show uniqueness, I realize that I will be done if I can show that $$ \forall a\;\forall b\;\forall c\;\left(c\text{ divides } ab\implies\exists m\;\exists n\; (m\text{ divides } a\;\wedge\; n\text{ divides } b\;\wedge\; c=mn)\right). $$

But after a lot of futile attempts, I'm not able to "see" any path leading me to this statement. Any help?

---

Note: I haven’t proven Euclid’s division lemma, and am not working with gcd’s. Hence I’ll appreciate a way that avoids these.

Answer 1

Proof of the uniqueness of prime factorization :

Let's suppose we have two factorizations : $p_1 ^{\alpha_1}...p_r ^{\alpha_r} = q_1 ^{\beta_1}...q_t ^{\beta_t}$.

Then for $1\leqslant i \leqslant r$, we have $p_i | q_1 ^{\beta_1}...q_t ^{\beta_t}$, and the $q_l$ are prime, so there exists one $1\leqslant j \leqslant t$ such that $p_i | q_j$ so $p_i = q_j$.

By doing the same with the $q_j$, we get that $\{p_1,...,p_r\} = \{q_1,...q_l\}$ and as all the $p_i$ and $q_j$ are different, we have that $r=l$.

We can then reorder the $(p_i)$ and $(q_j)$ to have $p_i = q_i$.

Let's prove we have $\alpha_i=\beta_i$ for $1\leqslant i\leqslant r$.

For $1\leqslant i\leqslant r$, $p_i^{\alpha_i} |q_1 ^{\beta_1}...q_r ^{\beta_r}$ and by Gauss Lemm, since $p_i$ is prime with all the $q_j$ for $j\geqslant 2$, we have $p_i^{\alpha_i} | q_i^{\beta_i} = p_i^{\beta_i}$, and we can do the same with $q_i$, so $p_i^{\alpha_i} = p_i^{\beta_i}$.

So $\alpha_i = \beta_i$, and this for all $i$.

Then the decomposition is unique.

For a proof of Euclid Lemma :

Let's suppose there exists $p$ prime and $a,b\in \mathbb{N}$ such that $p$ does not divide $a$ and $b$, but $p|ab$. Let's take, for $p$ and $a$ given, among all the possibilities of $b$, the smallest.

Then $0<b<p$ (because if not we could replace $b$ by a smaller one). We note $r$ the rest of Euclid's division of $p$ by $b$, which is not null since $p$ is prime. Then $p=mb+r$ so $ar = ap -mab$ is a multiple of $p$.

But we know that $0<r<b<p$ so $ar$ is not a multiple of $p$ because of the minimality of $p$.

So we've got a contradiction, and that proves Euclid's Lemma.

Answer 2

You can prove your displayed assertion by strong induction on $c$. The assertion is clearly true for the base case $c=1$ (with $m=n=1$). So assume it's true for all $c'\lt c$, where $c\gt1$. Let $p$ be any prime divisior of $c$ and write $c=pc'$, noting that $p\gt1$ implies $c'\lt c$.. Since $p\mid c\mid ab$, we know (by Euclid's lemma) that $p\mid a$ or $p\mid b$. Without loss of generality, let's assume it's $p\mid a$, and write $a=pa'$. We find now that $c'\mid a'b$, hence, by the strong induction hypothesis, there exist integers $m'$ and $n$ such that $m'\mid a'$, $n\mid b$, and $m'n=c'$. Now simply let $m=pm'$ and note that $m'\mid a'\implies m=pm'\mid pa'=a$ and $c=pc'=pm'n=mn$.