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

$\blacksquare$
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "http://hippomath.blogspot.com/2011/06/proof-reducing-prime-checking-bounds-to.html", "fetch_time": 1534839564000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2018-34/segments/1534221218070.73/warc/CC-MAIN-20180821073241-20180821093241-00337.warc.gz", "warc_record_offset": 179023913, "warc_record_length": 15490, "token_count": 342, "char_count": 987, "score": 4.34375, "int_score": 4, "crawl": "CC-MAIN-2018-34", "snapshot_type": "longest", "language": "en", "language_score": 0.7111008763313293, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00063-of-00064.parquet"}