# Thread: Proofs involving composite numbers

1. ## Proofs involving composite numbers

1) Prove that every composite number greater than 1 has at least one prime divisor.

To me, this sounds like the fundamental theorem of arithmetic (I could be dead wrong) and I have found various sites explaining that there are 2 parts to this proof...but I'm not sure if this is how I'm supposed to set it up.

2) Prove that every composite number n has at least one prime divisor which is =< sqrt(n).

3) Prove that every composite number can be represented as a product of primes.

The problem I'm having is that all these proofs seem very alike to me and I don't really know how to begin any of them. I know that every composite number can be broken down into a product of primes,but I don't really know how to show that explicitly.

Any help would be greatly appreciated!

2. #1: Let $n$ be the smallest integer with no prime divisors. Since $n$ is composite, we know that: $n = ab$ where $1 < a,b < n$. But since $n$ was the smallest integer with no prime divisors, then there exists some prime such that $p \mid a$. See the contradiction?

#2: Let $n = ab$ and $1 < a \leq b < n$. Suppose $a > \sqrt{n}$ (so $b > \sqrt{n}$ as well). What can you say about $ab$ then? How would you then bring the prime $p$ into this?

#3: This is pretty much the fundamental theorem of arithmetic (except for the uniqueness part). Again, we have another proof by contradiction. Suppose $n$ was the smallest number that couldn't be written as a product of primes. It must be composite (otherwise it would be prime!), i.e. $n=ab$. But since $n$ was the smallest such number, then $a$ and $b$ can be written as a product of primes. Can you piece all these together?

3. [QUOTE=o_O;287440]#1: Let $n$ be the smallest integer with no prime divisors. Since $n$ is composite, we know that: $n = ab$ where $1 < a,b < n$. But since $n$ was the smallest integer with no prime divisors, then there exists some prime such that $p \mid a$. See the contradiction?

Hi, thanks for the quick reply. I still am a little confused. Let me begin with #1.

It seems like to me that they key to this proof is the fact that 1<a,b<n...because then this tells us that n is not the smallest integer. Which then allows us to conclude that there is some prime number that divides a...so there is a contradiction. I don't really get the last part (meaning, how did we get to the fact that p|a from the fact that n is not the smallest integer anymore?)

Thanks.

4. Originally Posted by jusstjoe
how did we get to the fact that p|a from the fact that n is not the smallest integer anymore?
note that a and b are smaller than n. since n is the smallest integer with no prime divisors, it means that all integers smaller than it have prime divisors (otherwise, one of those integers would have been the smallest). do you see?

5. #2: Let $n = ab$ and $1 < a \leq b < n$. Suppose $a > \sqrt{n}$ (so $b > \sqrt{n}$ as well). What can you say about $ab$ then? How would you then bring the prime $p$ into this?

OK.

So I think given this situation, ab>n? I believe this is so because if a and b are both bigger than sqrt(n), then it must be that a*b>n,
but then this is a contradiction to our original statement, n=ab...but I don't know if I know how to bring prime numbers into this mix.

#2: Let $n = ab$ and $1 < a \leq b < n$. Suppose $a > \sqrt{n}$ (so $b > \sqrt{n}$ as well). What can you say about $ab$ then? How would you then bring the prime $p$ into this?