Thread: Proof that all numbers>1 are divisable by a prime.

I'm trying really hard to get good at making proofs. It is extremely hard for me, much more so than anything else I have ever done. I've tried to prove the title above but I don't know if my proof is logical.

lemma: "If n > 1 then there is a prime p such that p | n ."
n and k are integers.

proof:
Assume that there is no such p for n>1 such that

This would imply that for any prime value of p.
This also implies that there are no primes that can be expressed as the division of two integers.
However if this was true, prime numbers would be irrational which they are not.

Therefore all numbers>1 are divisable by a prime?
-------------------------------------------------------------------------
I'm not sure if this is logical. If it is not please don't post the proof, just give me a hint?

Originally Posted by integral

I'm trying really hard to get good at making proofs. It is extremely hard for me, much more so than anything else I have ever done. I've tried to prove the title above but I don't know if my proof is logical.

lemma: "If n > 1 then there is a prime p such that p | n ."
n and k are integers.

proof:
Assume that there is no such p for n>1 such that

This would imply that for any prime value of p.
This also implies that there are no primes that can be expressed as the division of two integers.
However if this was true, prime numbers would be irrational which they are not.

Therefore all numbers>1 are divisable by a prime?
-------------------------------------------------------------------------
I'm not sure if this is logical. If it is not please don't post the proof, just give me a hint?

If n itself is prime, it can be divided by itself, so can be divided by a prime.

If n is composite, it is the product of prime factors. So it can be divided by a prime.

I'm trying to assume I don't know the FTA. :/
So my proof is wrong?

Originally Posted by integral

I'm trying to assume I don't know the FTA. :/
So my proof is wrong?

What's the FTA? This is basic knowledge of numbers - a positive integer greater than 1 is always either prime or composite...

Funamental theorem of arithmatic.
"
If n is composite, it is the product of prime factors. So it can be divided by a prime." This statement is essentially what I am trying to prove,


EDIT: Fundamental theorem of arithmatic

Originally Posted by integral

Funamental theorem of algebra.
"
If n is composite, it is the product of prime factors. So it can be divided by a prime." This statement is essentially what I am trying to prove,

That's what a composite number is defined as - it doesn't need proof...

A composite number n is defined to be a number divisable a by 1,n, and k where k is some integer.
A composite number is NOT defined as the product of primes. That is the fundamental theorem of arithmatic which has many proofs "it doesn't need proof..."


EDIT: Fundamental theorem of arithmatic.

Originally Posted by integral

A composite number n is defined to be a number divisable a by 1,n, and k where k is some integer.
A composite number is NOT defined as the product of primes. That is the fundamental theorem of arithmatic which has many proofs "it doesn't need proof..."


EDIT: Fundamental theorem of arithmatic.

i see your dilemma. might i suggest you can proceed by strong induction? 2 is prime (base case).

now, we assume that for all 1 < k < n, k is divisible by a prime.

if n is prime, it is divisible by a prime, so assume n is composite. so n is divisible by r, where 1 < r < n.

by our assumption, r is divisible by some prime, say p, whence n is also divisible by p.

(the idea is: we know that if a number isn't prime, it has smaller factors. examining these smaller factors,

they may turn out to be prime, or not, but if not, then they have "smaller smaller factors". this process has to terminate

at some point, because the number of "smaller numbers" is finite, for any given n).

the fundamental theorem of arithmetic actually says more than just: any (non-negative integer) number is the product of prime factors. it says that

the set of factors is UNIQUE, and that the maximum power of any prime factor that divides n is likewise unique.