# Math Help - Number Theory

1. ## Number Theory

I need help with this problem please.
Why is it sufficient
to test that p does not have any divisors
≤ square root of p, to prove that the number p is prime or not.

2. ## Re: Number Theory

If x is a divisor of p then there exist an integer, y, such that p= xy. If x is larger than the square root f p, what must be true of y?

3. ## Re: Number Theory

Thank you for your time and effort.
This type of maths is new to me so it will take me some time to work it out.

4. ## Re: Number Theory

Maybe this will help.
Suppose p is an integer greater than 1 and p is not a prime. Let q be the smallest prime divisor of p. (You need to know that any integer greater than 1 is either a prime or a product of at least two primes.). Say $p = qr,\,q\leq r$ and so $q^2\leq qr=p$. That is, $q\leq\sqrt p$

So if you test all primes q with $q\leq \sqrt p$ and none of these divide p, then p must be prime: if p were not prime the above paragraph shows there is a prime q with $q\leq \sqrt p$ and q is a divisor of p.