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$?
Asked
Active
Viewed 298 times
1
-
3Because it leaves a remainder of $1$. – Brian M. Scott Jan 21 '13 at 23:50
-
1Dividing 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
-
1You 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 01:09
1 Answers
2
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!
ArthurStuart
- 4,932