16 Jun 2011

Proof - Reducing prime checking bounds to $\sqrt{n}$

This is a simple proof accompanying my last post on generating primes.

Let $n$ be a non-prime (i.e. composite), then it must have factors $a$ and $b$ less than $n$.
In other words: $n=ab$, with $n>a>1$ and $n>b>1$.
Suppose $a>\sqrt{n}$ and $b>\sqrt{n}$. This would mean $ab>n$. This cannot be as we just stated that $n=ab$.
Thus, the conclusion we draw is that either $a$ or $b$ is less than or equal to $\sqrt{n}$.
Let us say that  it is $a\leq \sqrt{n}$.
Since $a>1$ , there must exist a prime $p$ that divides $a$. Furthermore, $p\leq a$ since it divides $a$.
We saw earlier that $a$ divides $n$. Since $p$  divides $a$, our prime $p$ must divide $n$This gives us the result we are trying to prove: $p\leq a$ and $a\leq \sqrt{n}$. Therefore: $p\leq a\leq\sqrt{n}$.
Conclusion: If $n$ is not prime, it must have a prime factor (or regular factor) below $\sqrt{n}$. Otherwise, $n$ must be prime.



  1. This confuses me. Or rather, does not confuse me, for I am you, but I am sure that a lesser mind would be confused. Like me. But not me, because I am you.

  2. @Paul Liu
    My troll senses are tingling.