Searching for primes

This note exists mostly as a reminder for me but perhaps it will enlighten others too.

When searching for prime numbers, say checking the primality of n, we only have to search up until \sqrt{n}. But why? I tend to forget a lot, so perhaps writing it down will help remind me.

Let’s have a look at the conditions we require in order for n to be prime. We require that two numbers exist, both greater than 1, such that n=a \times b.

Well that’s fair enough – there’s not a whole lot to find disagreement with so far. Now, our statement that we can find one of these numbers (the lower one of course) by searching only up to \sqrt{n} means that the lower one of these numbers must be equal to or less than the square root of n. But how do we prove that?

Let’s go with a classic proof by contradiction – we’ll assume that neither of the numbers fulfills that condition. That is, both a and b are greater than \sqrt{n} .

However, this would mean that a \times b > n which cannot be the case if they are the two divisors of n.

This means that our assumption was wrong and that one of a and b must be less than or equal to \sqrt{n}. Therefore, in order to find this number, we need only search up until \sqrt{n}.

And that’s it – post a comment if you have any questions, although that seems unlikely. Hopefully this will stick in my brain now.

Tagged with:
Posted in Brain Pieces

Leave a Reply