Thread: 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.

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 are greater than

Then .

What can we conclude from this?

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 then 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 .

Thanks! Makes a lot more sense!