# Euclid's Proof of infinite prime numbers

I think this should probably be obvious, but I having trouble understanding part of the proof: If $N=p_1p_2\cdots p_n+1$, then why is it necessarily true that any given $p$ does not divide $N$?

-
Because it leaves a remainder of $1$. – Brian M. Scott Jan 21 '13 at 23:50
Dividing by any of the given $p_k$ leaves a remainder of $1$. – Henry T. Horton Jan 21 '13 at 23:50
Oh alright I see thanks – user58437 Jan 21 '13 at 23:51
You can also use $\, N = p_1 p_2\cdots p_k +\, p_{k+1}\cdots p_n,\ \$ or, more simply, note that $N(N+1)$ has more prime factors than $N.\ \$ – Math Gems Jan 21 '13 at 23:54
Caveat: Note that this does not generate all prime numbers, only creates a new one. For example, $2 \cdot 3 + 1 = 7$, but the next prime is $5$. – George V. Williams Jan 22 '13 at 1:09

Because the rest of division for all $p_{i}$ is $1$. For example we can suppose that there are only $3$ prime numbers: $(2,3,5)$. So you can define a new number $N$ as $2*3*5+1=31$. So it results that $31=2*15+1=6*5+1=3*10+1$. Then $N$ is a new prime number!

-
Or is divisible by a new prime number, in general. – Charles Jan 22 '13 at 0:17
{"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://math.stackexchange.com/questions/283889/euclids-proof-of-infinite-prime-numbers", "fetch_time": 1469563351000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2016-30/segments/1469257825124.22/warc/CC-MAIN-20160723071025-00308-ip-10-185-27-174.ec2.internal.warc.gz", "warc_record_offset": 160923736, "warc_record_length": 17504, "token_count": 402, "char_count": 1173, "score": 3.828125, "int_score": 4, "crawl": "CC-MAIN-2016-30", "snapshot_type": "latest", "language": "en", "language_score": 0.8386349678039551, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00001-of-00064.parquet"}