3
$\begingroup$

Prove that $p_1p_2p_3\cdots p_n+1$, where $p_n$ is the $n^{th}$ prime, cannot be the square of an integer.

Let $p_1p_2p_3\cdots p_n+1=Q$ and assume it is the square of an integer, so $\sqrt{p_1p_2p_3\cdots p_n+1}$ is an integer and can therefore be written as $p_ap_bp_cp_d\cdots$ and let $p_ap_bp_cp_d\cdots=R$. Now $Q/R$ should be equal to $R$, so we have $(p_1p_2p_3\cdots p_n+1)/(p_ap_bp_cp_d\cdots)$, or $I+1/(p_ap_bp_cp_d\cdots)$, where $I$ is an integer. However, $I+$ a fraction is clearly not an integer, so this is a contradiction. (Note: I know this can be done with modular arithmetic, but I haven't learned it yet).

$\endgroup$
  • 1
    $\begingroup$ How can you conclude that $\frac{Q-1}{R}$ is an integer without knowing what $p_a,p_b,$ etc. actually are? $\endgroup$ – Cameron Buie Apr 21 '13 at 15:36
  • $\begingroup$ I'm sorry, this is invalid. I made a mistake and for a second I got confused myself and thought that $p1*p2*..$ is the square of $pa*pb*...$ and concluded that this is an integer, I forgot that $pa*pb*...$ is actually the square root of &p1*p2*...+1$. $\endgroup$ – Ovi Apr 21 '13 at 15:45
  • $\begingroup$ Hint $\rm\ \ 2(2k+1) = (n-1)(n+1)\:\Rightarrow\:4\,$ divides the RHS but not the LHS, contradiction. $\endgroup$ – Math Gems Apr 21 '13 at 15:52
  • $\begingroup$ Somebody has already asked a similar question less than an hour ago, and received a very neat answer. $\endgroup$ – barak manos Feb 6 '15 at 17:21
12
$\begingroup$

Your conclusion is wrong, because you are careless with your notation. Let me spell out the proper notation, which would indicate where you made a mistake. (Note that this does not invalidate that you proof might eventually lead to an answer, merely that your proof is currently incorrect.)

Suppose we have $Q = 1 + \prod_{i=1}^M p_i = R^2$ for some $M, R$ positive integers.
Let $R= p_a ^ {r_a} \times p_b ^{r_b} \times \ldots \times p_k ^{r_k}$, where $p_i$ are arranged in increasing order, $r_i$ are the exponents. Moreover, let $ p_l \leq p_M$. Then, your conclusion is that

$$R = p_a ^ {r_a} \times p_b ^{r_b} \times \ldots \times p_k ^{r_k} = \frac{Q}{R} = \frac { 1 + \prod_{i=1}^M p_i} {p_a ^ {r_a} \times p_b ^{r_b} \times \ldots \times p_k ^{r_k}} $$

Now, we may not easily pull out your integer value of $I$, because
1. $r_i$ need not be 1.
2. There could be some primes which are larger than $p_M$.


How about parity instead of modulo arithmetic? Very similar concepts though.

Proof by contradiction. Suppose that $1+ \prod_{i=1}^k p_i = N^2$ for some $k, N$ positive integers.

Then, $N^2 -1 = (N-1)(N+1) = \prod_{i=1}^k p_i$.

Since $p_1 = 2$, the RHS is even, which implies that either $N-1$ or $N+1$ is even. In either case, it implies that the other term is also even, hence the LHS is a multiple of $2 \times 2 = 4$. Thus, we get that the product of primes (LHS) is a multiple of 4, which contradicts the fact that there is only 1 even prime.

$\endgroup$
  • $\begingroup$ The thing to learn from this for the OP: The square of an even number is always a multiple of $4$, the square of an odd number is always one more than a multiple of $8$(!) $\endgroup$ – Hagen von Eitzen Apr 21 '13 at 15:50
  • $\begingroup$ @Calvin I don't see why $(N-1)$ and $(N+1)$ are both necessarily prime $\endgroup$ – Ovi Apr 21 '13 at 15:57
  • 1
    $\begingroup$ @Ovi $(N-1)$ and $(N+1)$ aren't both necessarily prime, but Calvin's proof doesn't anywhere imply that they need to be; whether they're prime or not, it's still the case that $N^2-1 = (N-1)(N+1)$ and that if one of $(N-1)$, $(N+1)$ is even then so is the other. $\endgroup$ – Steven Stadnicki Apr 21 '13 at 16:36
  • $\begingroup$ Oh I see If they are both even then $N^2-1$ has a factor of 4 and there is at most a factor of 2 in $N^2-1$. I thought Calvin was trying to say that N plus or minus 1 are prime and there is only 1 even prime. Well thanks for clearing my confusion $\endgroup$ – Ovi Apr 21 '13 at 17:54
2
$\begingroup$

I'm the asker reviewing this question a few years later...

Now it's easy: squares are $\equiv 0, 1 \pmod 4$. Since $p_1 p_2 \cdots p_n$ has only one factor of $2$, it is $\equiv \pm2 \pmod 4$, so $p_1 p_2 \cdots p_n + 1 \equiv 3 \pmod 4$, thus it cannot be a square.

$\endgroup$

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.