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.)


1 Answer 1


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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .