# A prime number problem.

If $n$ is a positive integer and $(p_1,p_2,p_3,p_4,\ldots, p_n)$ are distinct positive primes, show that the integer $(p_1\cdot p_2\cdot p_3\cdot p_4\cdots p_n)+1$ is divisible by none of these primes. How do I figure out that none of the primes divide that new integer?

• Start with a simple case. Does $p_1$ divide $p_1p_2$? Does $p_1$ divide $p_1p_2 + 1$? – Chris Culter May 4 '16 at 20:27
• No it can't. I know it can't be possible, but to prove it, do I do induction? – nyorkr23 May 4 '16 at 20:29
• You don't need induction. $d$ cannot divide $kd+1$? – almagest May 4 '16 at 20:29
• Oh, that's what I was after. Thanks. – nyorkr23 May 4 '16 at 20:31
• You don't even need them to be primes. It suffices to have $p_i\ge2$. – Hagen von Eitzen May 4 '16 at 20:37

Suppose $7$ is one of the primes, so $p_1\cdots p_n$ is a multiple of $7$.

The next multiple of $7$ after $p_1\cdots p_n$ is $(p_1\cdots p_n)+7$. So $(p_1\cdots p_n)+1$ is not a multiple of $7$.

More formally, suppose $7$ divides $(p_1\cdots p_n)+1$. Then for some integers $j$, $k$, \begin{align} (p_1 \cdots p_n) & = 7j \tag 1 \\ (p_1 \cdots p_n) + 1 & = 7k \tag 2 \\[10pt] \text{Then subtracting (1) from (2), we get: } 1 & = 7k - 7j = 7(k-j) \\ \end{align} So $1 = 7(k-j)$.

• But how exactly do I show that as a proof? – nyorkr23 May 4 '16 at 20:30
• Do you have the theorem sometimes called the "division algorithm", stating that for $m,n\in\mathbb N$, there exists a quotient $q$ and a remainder $r\in\{0,1,2,\ldots,n-1\}$ such that $m = qn+r$? $\qquad$ – Michael Hardy May 4 '16 at 20:32
• Yes, I've learned that algorithm. – nyorkr23 May 4 '16 at 20:36
• I've expanded the answer somewhat. $\qquad$ – Michael Hardy May 4 '16 at 20:39

We will need the following theorem:

Theorem. For any two natural numbers $x, y$ ($y \geq 1$), there are unique natural numbers $q, r$ where $0 \leq r < y$ such that $x = qy + r$.

Proof. If $x < y$ then we must have $q = 0$ and $r = x$, so in this case the $q, r$ exist and are unique. Assume that there is a natural number $x \geq y$ such that no such $q, r$ exist, then without loss of generality we may assume that $x$ is the smallest such number. However, then $x - y$ cannot be written in the desired form either, as if we had $x - y = qy + r$ then this would imply $x = (q+1)y + r$. This contradicts the minimality of $x$, as $x - y$ is a smaller natural number with the same property. Therefore, such $q, r$ must exist for all values of $x$.

To prove uniqueness, assume that we had $x = q_1 y + r_1 = q_2 y + r_2$ and $r_1 > r_2$, then $r_1 - r_2 = y(q_2 - q_1)$. On the other hand, $r_1 - r_2 \leq r_1 < y$, so that we have $y(q_2 - q_1) < y$ and therefore $q_1 = q_2$. QED.

Corollary. $x = qn + 1$ ($q, n \in \mathbb{N}$) is not divisible by $q$ for any $q \geq 2$.

Proof. If it were, we would have $x = qm$ for some $m$ and $x = qn + 1$ simultaneously, contradicting the uniqueness proved in the above theorem.

The statement in the question follows immediately from the corollary.

• The division algorithm (Theorem) is not needed. Simpler: if $\, qm = qn+1\,$ then $\,q(m-n) = 1,\,$ contra $\, q> 1$. – Bill Dubuque May 4 '16 at 21:55
• That is simpler, although I see no harm in using the division algorithm either way. – Starfall May 4 '16 at 21:58
• The simpler method is much more general: it works in any ring for any nonunit $q$, i.e. any $q$ that does not divide $1$. But most rings don't have a division algorithm. That said, it is, of course, always helpful to have multiple proofs. Here one gains a bit different insight by using the uniqueness of remainders in the division algorithm - as you do. I've written about the power of uniqueness theorems in many of my posts, e.g. see here. – Bill Dubuque May 4 '16 at 22:02