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.

Printable View

- Nov 15th 2012, 05:04 AMGpinkFundamental 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 AMGpinkRe: Fundamental theory of arithmetic
Can anybody please help me please?

- Nov 15th 2012, 12:39 PMemakarovRe: 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 PMDevenoRe: 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:

with .

now so for some i = 1,2,...,s.

this, in turn, implies . since is prime, and , we conclude .

thus since ,

we conclude that 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 IS unique,

p_{i}= q_{i}for all i > 1, and k_{i}= m_{i}, for all i > 1.

thus the only difference between:

is the power of p_{1}.

but , so we must have k_{1}= m_{1}, and a does not exist, which proves the theorem.