# Prove composite number has a prime divisor

• Jan 25th 2011, 04:08 PM
kathrynmath
Prove composite number has a prime divisor
Prove that if integer n>=2 is composite, then n has a prime divisor which is <=(n)^1/2

My first thought was to somehow use the fundamental theorem of arithmetic.
I have n=p1p2...pr.
I assumed each integer >=2 can be factored into primes.
Then assuming k+1 is composite, we have k+1=ab where 2<=a,k+1 and 2<=b<k+1. But at this step I get stuck.
• Jan 25th 2011, 04:13 PM
chiph588@
Quote:

Originally Posted by kathrynmath
Prove that if integer n>=2 is composite, then n has a prime divisor which is <=(n)^1/2

My first thought was to somehow use the fundamental theorem of arithmetic.
I have n=p1p2...pr.
I assumed each integer >=2 can be factored into primes.
Then assuming k+1 is composite, we have k+1=ab where 2<=a,k+1 and 2<=b<k+1. But at this step I get stuck.

Assume otherwise, so that all prime divisors of $n$ are greater than $\sqrt{n}$

Then $n=p_1^{a_1} p_2^{a_2}\cdots p_k^{a_k} > \sqrt{n}^{a_1}\sqrt{n}^{a_2}\cdots \sqrt{n}^{a_k}$.

What can we conclude from this?
• Jan 25th 2011, 04:27 PM
HallsofIvy
If the positive number,n, is composite, then there exist integers a and b such that ab= n. If both a and b were larger than $\sqrt{n}$ then $n= ab> (\sqrt{n})(\sqrt{n})>$ which is impossible. That is either a or b is less than n. We can, without loss of generality, assume it is a that is less than n. If a is prime, we are done. If a is not prime, then it has prime factors that are less than a and so less than $\sqrt{n}$.
• Jan 25th 2011, 04:44 PM
kathrynmath
Thanks! Makes a lot more sense!