Re: 2012 HSC MX2 Marathon
New question: Prove by induction that every natural number greater than 2 has a prime divisor.
There is a stronger result, that every natural number greater than 1 has a prime divisor. Anyhow, several methods, first as per the question states:
Assume a set
where
, then n > 1 and n has a prime divisor. Now to show that k exists in Q is quite straightforward with the following partition:
If k has no other factors than k or 1, then k is trivially in Q.
If k is nonprime, then k will have a factor w such that
, thus
by the inductive hypothesis.
hence
Next method is to show a even stronger result, in other words, the fundmental theorem of arithmetic.
Assume that there are numbers which can not be expressed as a product of primes. Let the smallest possible number of this kind be
.
can not be
since
is neither composite nor prime.
can not be prime since the PPF of a prime number is just itself. Thus
must be a composite number.
Let the composition of
where
Since
was the smallest number that can not be expressed as a product of primes, this means
and
can be expressed as a product of primes and consequently we get
where
and
can be both expressed as primes. Contradiction!
Thus
can also be expressed as a product of primes.
Lemma 1: If
is a prime and
then
for some
.
Lemma 2: If
and
are primes and
is a natural number and
then
.
Let's assume that for some number
that there are
(at least) ways of expressing its PPF.
Clearly for all
,
By
Lemma 1 for any
.
By
Lemma 2
This means that for all
and all
there are values of
which equals to those of
. For example,
could equal to
, or
etc. This also means we have created a bijection between
and
such that
.
Therefore if the number
has
PPF's then the prime number 'base' will be exactly the same, the only different would be in the powers, namely
and
.
Now since each
has a corespondent equivalent
we can rewrite
as:
however
can not be divided by
unless for some
such that
But since
we have a contradiction.