# Prime number problem

• Nov 1st 2007, 04:35 AM
Revilo
Prime number problem
Let n be a positive integer with n not equal to 1. Suppose that n is not a prime number. Show that there is a prime number p such that p divides n and p is less than or equal to the square root of n.

I have no idea where to start with this. Any help would be appreciated.
• Nov 1st 2007, 05:28 AM
angel.white
Quote:

Originally Posted by Revilo
Let n be a positive integer with n not equal to 1. Suppose that n is not a prime number. Show that there is a prime number p such that p divides n and p is less than or equal to the square root of n.

I have no idea where to start with this. Any help would be appreciated.

Okay, n is an integer and is not prime, this means it has a positive divisor other than itself, and that divisor is prime (based on the Fundamental Theorem of Arithmetic which says: Every positive integer greater than 1 can be written uniquely as a prime or as the product of two or more primes where the prime factors are written in order of nondecreasing size.)

So we know that some prime number divides n, we'll name that prime number $\displaystyle p_1$, and say that the quotient is some integer a (it must be an integer because if it wasn't, then p would not divide n)

right, so $\displaystyle p_1 *a = n$ (which coincidentally spells pan, but that's not part of the proof)

Now, either $\displaystyle p_1$ or a is < $\displaystyle \sqrt{n}$ because if neither was, then both would be greater than the $\displaystyle \sqrt{n}$ And if they were both greater than the $\displaystyle \sqrt{n}$ we could say that $\displaystyle p_1 * a$ > n However, $\displaystyle \sqrt{n} * \sqrt{n} = n$ and $\displaystyle a*p_1 = n$ so this is a contradiction.

This means that either $\displaystyle p_1$ or a is not greater than $\displaystyle \sqrt{n}$ therefore either $\displaystyle p_1$ or a must be less than $\displaystyle \sqrt{n}$.

If $\displaystyle p_1$ is less than $\displaystyle \sqrt{n}$ then there is a prime number which divides n and is less than the $\displaystyle \sqrt{n}$. If $\displaystyle p_1$ is greater than $\displaystyle \sqrt{n}$, then a must be less than $\displaystyle \sqrt{n}$. And by the Fundamental Theorem of Arithmetic, a is either prime, or the product of two or more primes, so either a or one of its factors is prime. So there is a prime number less than $\displaystyle \sqrt{n}$ which divides n.

It's also worth pointing out that there is a theorem which says if a divides b, and b divides c, then a divides c. This is for if your instructor wants you to show that if a is less than the $\displaystyle \sqrt{n}$, but a is not prime, then one of a's prime factors will divide n.