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 , we only have to search up until . 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 to be prime. We require that two numbers exist, both greater than 1, such that .

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 means that the lower one of these numbers must be equal to or less than the square root of . 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 .

However, this would mean that which cannot be the case if they are the two divisors of .

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

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