Prime number problem

**Revilo** · November 1st 2007, 04:35 AM

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.

**angel.white** · November 1st 2007, 05:28 AM

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 $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 $p_1 *a = n$ (which coincidentally spells pan, but that's not part of the proof)

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

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

If $p_1$ is less than $\sqrt{n}$ then there is a prime number which divides n and is less than the $\sqrt{n}$ . If $p_1$ is greater than $\sqrt{n}$ , then a must be less than $\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 $\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 $\sqrt{n}$ , but a is not prime, then one of a's prime factors will divide n.

Thread: Prime number problem

LinkBack

Thread Tools

Display