The Student Room Group
Uni students - Complete our survey >>
Uni students - Complete our survey >>
Uni students - Complete our survey >>

Can anybody help me with complete induction?

Prove that any natural number n>=2 either is prime or fators into a product of primes.

Thank you in advance....
Reply 1
Avatar for ttoby
ttoby
15
The approach you would want to take here is to look closely at the definition of a prime number.

If you take a number n, then if n is prime then you're done. If n isn't prime then you need to look at how it can be split into two factors (which aren't 1 and n) and see that, by the inductive assumption, each of those two factors can be expressed as a product of primes.
Reply 2
Avatar for Artus
Artus
OP
Original post by ttoby
The approach you would want to take here is to look closely at the definition of a prime number.

If you take a number n, then if n is prime then you're done. If n isn't prime then you need to look at how it can be split into two factors (which aren't 1 and n) and see that, by the inductive assumption, each of those two factors can be expressed as a product of primes.


I understand what you are saying but don't know how to show it. I tried to describe it in words, but my professor said my answer was incomplete.
Reply 3
Avatar for ttoby
ttoby
15
Did your professor say which part(s) of your answer were incomplete?

What you would want to include is:

A statement saying that 2 is prime
Something along the lines of 'suppose that, for some n natural, n>2, all of the numbers in the set {2, 3, ..., n-1} are either prime or could be expressed as product of primes'
Say that if n is prime then we are done.
If n is not prime then n can be expressed as n=ab where a, b are in {2, 3, ..., n-1}
Then you would need to say that a and b can be expressed as a product of primes by inductive assumption a=p1p2⋯pmaa=p_1p_2\cdots p_{m_a} and b=q1q2⋯qmbb=q_1q_2\cdots q_{m_b}
Hence n=ab=p1p2⋯pmaq1q2⋯qmbn=ab=p_1p_2\cdots p_{m_a}q_1q_2\cdots q_{m_b} so n can be expressed as a product of primes
Then you would need to put a statement at the end about how the result follows by induction.

Quick Reply

Related discussions

Latest

Trending

Trending

Articles for you