is this simple proof by contradiction of uniqueness of prime factorization correct?

137 Views Asked by At

I want to ask if the following proof correct. Assume that we have a prime factorization $$ n=\prod_{i=1}^{r}p_{i}^{e_{i}} $$

where $p_i$ is the $i$th prime number, $e_i$ are non-negative integers, and $p_r$ is the largest prime number $\leq n$.

Suppose there also exists a set of non-negative integers $f_i$ such that

$$ n=\prod_{i=1}^{r}p_{i}^{f_{i}}. $$

Hence, we have

$$ \prod_{i=1}^{r}p_{i}^{e_{i}} = \prod_{i=1}^{r}p_{i}^{f_{i}} $$

Now suppose $f_k > e_k$ for some $1\leq k \leq r$. Dividing both sides by $p_k^{e_k}$, we have

$$ \prod_{i\neq k}p_{i}^{e_{i}}=p_{k}^{f_{k}-e_{k}}\prod_{i\neq k}p_{i}^{f_{i}} $$

Clearly, $p_k$ divides the right-hand side, but does not divide the left. Hence, this contradiction means that our initial assumption that $f_k > e_k$ is impossible. By symmetry, we also cannot have $e_k > f_k$. Hence $e_i = f_i$ for all $i$, and the factorization is unique.

1

There are 1 best solutions below

0
On BEST ANSWER

The proof uses a fact that should be proved beforehand, namely that, for all primes $p$, if $p\mid ab$, then $p\mid a$ or $p\mid b$.

As such it is not fully correct. You can fix it using strong induction. If some number admitting distinct factorizations exists, then there is the minimum such $n$. Your argument shows that $n'=n/p_k^{f_k-e_k}$ also has distinct factorizations, which is a contradiction because $n'<n$.