# 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