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.

Printable View

- May 6th 2014, 01:55 PMmlgNumber 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, 02:23 PMHallsofIvyRe: 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, 03:13 PMmlgRe: 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, 09:47 PMjohngRe: 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, 01:12 AMmlgRe: Number Theory
Thank you for your time and effort and your excellent explanation.