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$.

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.

$\blacksquare$

$\blacksquare$

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.

ReplyDelete@Paul Liu

ReplyDeleteMy troll senses are tingling.