I'm trying to prove that factorization into primes is unique using mathematical induction. Here is my attempt and I would like to know if my reasoning is valid (and advice for any improvements if possible). Thank you.
Proof: Let $A(n)$ be the statement 'Natural number $n$ is unique in prime factorization.'
Initial step: case n = 1,2 is trivial.
Inductive step: Suppose $A(1), A(2), … A(k)$ are all true for some $k$. If $k+1$ is a prime, it is unique. If $k+1$ is not a prime, it can be written as a product of two natural numbers both smaller than $k+1$, let's say $ k+1 = ab$. Since $a,b$ is both less than $k + 1,$ $A(a), A(b)$ is true so $a$ and $b$ can be written as a unique factorization of prime as follows: $a = p_1^{a_1}p_2^{a_2}…p_i^{a_i}$ and $b = q_1^{b_1}q_2^{b_2}…q_i^{b_i}$. So $k + 1 = ab = p_1^{a_1}q_1^{b_1}p_2^{a_2}q_2^{b_2}…p_i^{a_i}q_i^{b_i}.$ If $p_k = q_k$ then $p_k^{a_k}q_k^{b_k}$ can be written as $p_k^{a_k + b_k}$. Since $k + 1$ is in form $p_1^{e_1}p_2^{e_2}…p_i^{e_i}$, base are unique since they are prime and exponents are unique since they are natural numbers. Therefore all natural numbers can be expressed in unique prime factors by induction.
Best Answer
The ingredient you're missing is that if $k+1=\prod_{i\in S}p_i^{A_i}=\prod_{j\in T}q_j^{B_j}$ then$$p_i|k+1=\prod_jq_j^{B_j}\implies\exists j\in T(p_1|q_j)$$where $\implies$ needs a proof by induction on $m:=\sum_jB_j$ of the fact that, if a product of $m$ integers is divisible by a prime $p$, at least one factor is. Hence if $k+1$ has multiple prime factorizations so does $(k+1)/p\le k$, contradicting the null hypothesis.
In case the proof of this theorem about $m$ products is unfamiliar, we proceed as follows:
Soo $m=2$ is the hard part. If $p=uv$ but $p\nmid u$, there are integers $x,\,y$ with $xp+yu=1$ by Bézout's lemma. So $p|xpv+yuv=p$ (because $p|uv$).