# Number Theory

• May 6th 2014, 12:55 PM
mlg
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.
• May 6th 2014, 01:23 PM
HallsofIvy
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?
• May 6th 2014, 02:13 PM
mlg
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.
• May 6th 2014, 08:47 PM
johng
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.
• May 7th 2014, 12:12 AM
mlg
Re: Number Theory