# What's wrong with this proof of unique factorization?

I've never seen this proof of the unique factorization theorem (aka the fundamental theorem of arithmetic). This doesn't mean much, since my reading in number theory is scant.

I like the proof, because it seems so straightforward, but precisely for this reason I have the strong suspicion that I made a mistake somewhere. I'd appreciate it if someone would point it out.

For any natural number (i.e. positive integer) $n$ and any prime number $p$, we can write

$$n = p^s t$$

for some integers $s \geq 0$ and $t$, with $p\nmid t$.

Next we show that, for any $n$ and $p$, such factorization is unique. (The whole proof rests on this uniqueness.)

If there are two such factorizations $p^s t$ and $p^{s^\prime} t^{\prime}$ of $n$, and, if we assume, without loss of generality, that $s \geq s^{\prime}$, then

$$p^s t = p^{s^\prime} t^{\prime} \; \Rightarrow \; p^{s - s^\prime} t = t^\prime \; \Rightarrow \; s = s^\prime \;,$$

since, by assumption, $p \nmid t^\prime$. Therefore, $t^\prime = p^0 t = t$.

The foregoing implies that there exist functions $\nu_p:\mathbb{Z}\backslash \{0\}\rightarrow \mathbb{Z}^{\geq 0}$ and $\delta_p:\mathbb{Z}\backslash \{0\}\rightarrow \mathbb{Z}\backslash p\mathbb{Z}$ such that, for all $n\in\mathbb{Z}\backslash \{0\}$,

$$n = p^{\nu_p(n)}\,\delta_p(n)\,.$$

Furthermore, if we enumerate the prime numbers in ascending order $p_1 = 2, p_2 = 3, \dots$, we can define $k(n)$ such that $p_{k(n)}$ is the largest prime number that is $\leq n$.

Now, any natural number $n$ can be written in the form

$$n = \prod_{i=1}^{k(n)} p_i^{a_i}\,.$$

...for some non-negative integers $a_1, a_2, \dots, a_{k(n)}$. The foregoing argument implies that $a_i = \nu_{p_i}(n), \; \forall i \in \{1, 2, \dots, k(n)\}$. EDIT: WRONG!

Now, if $q_1^{b_1}q_2^{b_2}\dots q_s^{b_s}$ (with $q_i$ prime, and $b_i > 0, \; \forall i \in \{1, 2, \dots, s\}$) is any factorization of $n$, then, $\forall i \in \{1, 2, \dots, s\},\, q_i = p_j$ for some $j \in \{1, 2, \dots, k(n) \}$. Therefore $\nu_{p_j}(n) = \nu_{q_i}(n)$. Furthermore,

$$q_i \nmid \prod_{j \neq i} q_j^{b_j},\;\;\;\;\;\;\text{[EDIT: WRONG!]}$$

and thus, by the uniqueness of the factorization $n = p_j^{\nu_{p_j}(n)}\delta_{p_j}(n)$, we conclude that $b_i = \nu_{p_j}(n) = \nu_{q_i}(n)$, and $\delta_{p_j}(n) = \delta_{q_i}(n) = \prod_{j \neq i} q_j^{b_j}$.

Furthermore, for every $j$ such that $\nu_{p_j}(n) > 0$, there must be an $i$ such that $q_i = p_j$, otherwise, the factorization $q_1^{b_1}q_2^{b_2}\dots q_s^{b_s}p_j^0$ would contradict the uniqueness of the factorization $n = p_j^{\nu_{p_j}(n)}\delta_{p_j}(n)$. [EDIT: WRONG!]

We conclude that $b_i = \nu_{q_i}(n), \; \forall i \in \{1, 2, \dots, s\}$, and therefore the factorization $q_1^{b_1}q_2^{b_2}\dots q_s^{b_s}$ is unique.

I must have made a mistake somewhere, because this seems too easy.

EDIT: Indeed there is not one but rather several errors, which I indicate above (I realized a couple of them on my way to work, and Ted added one more I did not think of.)

-
–  Jp McCarthy Apr 17 '13 at 14:39

At the very end, you do not know that a factorization like $n = q_1 q_2 p^0$ will contradict the uniqueness of $n = p^{v_p(n)} \delta_p(n)$. In order for the uniqueness property to apply, you need to know that $p \not | q_1 q_2$. There is no basis for concluding this, because in fact, $n = q_1 q_2$, so $p$ does divide $q_1 q_2$.
EDIT: Even before that, there is another problem. If you have a factorization like $n = q_1 q_2 q_3$, you do not know that $q_1\not| q_2 q_3$ in order to apply the uniqueness property.