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?
1
$\begingroup$
$\endgroup$
-
$\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
2
$\begingroup$
$\endgroup$
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)$.
answered May 4 '16 at 20:29
-
-
$\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$ I've expanded the answer somewhat. $\qquad$ $\endgroup$ – Michael Hardy May 4 '16 at 20:39
1
$\begingroup$
$\endgroup$
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
