Hi,
I want to prove fundamental theorem of arithmetic by using strong induction and proof by smallest counterexample.
Can someone by any chance help me? (with great detail please)?
I would appreciate people's help.
if the theorem is not true, there exists a minimal counter-example, a.
by supposition, there exists two distinct prime factorizations of a:
$\displaystyle a = p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r} = q_1^{m_1}q_2^{m_2}\cdots q_s^{m_s}$ with $\displaystyle p_1 < p_2 < \cdots < p_r, q_1 < q_2 < \cdots < q_s$.
now $\displaystyle p_1|a$ so $\displaystyle p_1|q_i^{m_i}$ for some i = 1,2,...,s.
this, in turn, implies $\displaystyle p_1|q_i$. since $\displaystyle q_i$ is prime, and $\displaystyle p_1 \neq 1$, we conclude $\displaystyle p_1 = q_i$.
thus since$\displaystyle \frac{a}{p_1^{k_1}} < a$,
we conclude that $\displaystyle p_2^{k_2}\cdots p_r^{k_r} = \frac{q_1^{m_1}q_2^{m_2}\cdots q_s^{m_s}}{q_i^{m_i}}$ are, in fact, the same factorization.
hence since we have r-1 factors on the left, and s-1 factors on the right:
r - 1 = s - 1, so r = s.
we now have two possibilities:
i = 1 (on the RHS),
i ≠ 1.
if i ≠ 1, then q_{1} = p_{2}, which implies p_{2} = q_{1} < q_{i} = p_{1}, contradicting our original factorization of a.
thus we must have p_{1} = q_{1}, and since the factorization of $\displaystyle \frac{a}{p_1^{k_1}}$ IS unique,
p_{i} = q_{i} for all i > 1, and k_{i} = m_{i}, for all i > 1.
thus the only difference between:
$\displaystyle a = p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r} = p_1^{m_1}p_2^{k_2}\cdots p_r^{k_r}$
is the power of p_{1}.
but $\displaystyle p_1^{k_1} = \frac{a}{p_2^{k_2}\cdots p_r^{k_r}} < a$, so we must have k_{1} = m_{1}, and a does not exist, which proves the theorem.