Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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!

share|cite|improve this answer
Or is divisible by a new prime number, in general. – Charles Jan 22 '13 at 0:17

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.