# Fundamental theory of arithmetic

• Nov 15th 2012, 05:04 AM
Gpink
Fundamental theory of arithmetic
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.
• Nov 15th 2012, 07:51 AM
Gpink
Re: Fundamental theory of arithmetic
• Nov 15th 2012, 12:39 PM
emakarov
Re: Fundamental theory of arithmetic
I am not sure about smallest counterexamples, but for the inductive proof of the fundamental theorem of arithmetic see Wikipedia.
• Nov 15th 2012, 03:43 PM
Deveno
Re: Fundamental theory of arithmetic
if the theorem is not true, there exists a minimal counter-example, a.

by supposition, there exists two distinct prime factorizations of a:

$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 $p_1 < p_2 < \cdots < p_r, q_1 < q_2 < \cdots < q_s$.

now $p_1|a$ so $p_1|q_i^{m_i}$ for some i = 1,2,...,s.

this, in turn, implies $p_1|q_i$. since $q_i$ is prime, and $p_1 \neq 1$, we conclude $p_1 = q_i$.

thus since $\frac{a}{p_1^{k_1}} < a$,

we conclude that $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 q1 = p2, which implies p2 = q1 < qi = p1, contradicting our original factorization of a.

thus we must have p1 = q1, and since the factorization of $\frac{a}{p_1^{k_1}}$ IS unique,

pi = qi for all i > 1, and ki = mi, for all i > 1.

thus the only difference between:

$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 p1.

but $p_1^{k_1} = \frac{a}{p_2^{k_2}\cdots p_r^{k_r}} < a$, so we must have k1 = m1, and a does not exist, which proves the theorem.