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?

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

  • $\begingroup$ But how exactly do I show that as a proof? $\endgroup$ – nyorkr23 May 4 '16 at 20:30
  • $\begingroup$ 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$ $\endgroup$ – Michael Hardy May 4 '16 at 20:32
  • $\begingroup$ Yes, I've learned that algorithm. $\endgroup$ – nyorkr23 May 4 '16 at 20:36
  • $\begingroup$ I've expanded the answer somewhat. $\qquad$ $\endgroup$ – 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.

  • 1
    $\begingroup$ The division algorithm (Theorem) is not needed. Simpler: if $\, qm = qn+1\,$ then $\,q(m-n) = 1,\,$ contra $\, q> 1$. $\endgroup$ – Bill Dubuque May 4 '16 at 21:55
  • $\begingroup$ That is simpler, although I see no harm in using the division algorithm either way. $\endgroup$ – Starfall May 4 '16 at 21:58
  • $\begingroup$ 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. $\endgroup$ – Bill Dubuque May 4 '16 at 22:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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