I am trying to prove the following: If $p$ and $q$ are prime numbers larger than $2$, then $pq + 1 $ is never prime. Any ideas?

  • 14
    $\begingroup$ It is even, since $p,q>2$. $\endgroup$ – Eclipse Sun Oct 26 '14 at 13:50

Curious that none of the answers so far gets this very simple argument completely right (without implicitly assuming at some point that primes are always odd). [At least they didn't at the time of writing.]

Let $p,q$ be odd primes. Then since $p,q$ are odd, $pq+1$ is even. If it were prime, one would have $pq+1=2$ since that is the only even prime number. But then $pq=1$ while odd primes are${}\geq3$, clearly a contradiction.

(Alternatively for the final phrase: "but $1$ has no prime divisors at all" or "but $1$ is not a prime number".)

  • 6
    $\begingroup$ What's wrong with assuming that primes "at some point" (i.e. after 2) are always odd? The indivisibility of integers by integers other than itself and one is the very definition of primality. Since any even number >= 2 is divisible by two, the assumption that all primes > 2 are odd is completely valid. $\endgroup$ – par Oct 27 '14 at 6:16
  • $\begingroup$ @par: I meant at some point in the argument ("after $2$" is not "at some point"). For instance Digital Brain starts saying (all) primes are odd; Jasper Joy and AaronMaroja just show evenness (and JiK only vaguely alludes to it), suggesting that this implies non-primeness. I do know there that $p>2$ prime implies $p$ odd; indeed my argument mentions that $2$ is the only even prime number. $\endgroup$ – Marc van Leeuwen Oct 27 '14 at 6:28
  • $\begingroup$ I see what you mean. The question specifically says "odd primes", and I think that's so fundamental that you don't have to explicitly call out 2 as the only even prime. That said, you did make clever use of that fact in your proof. I always enjoy a proof by contradiction. $\endgroup$ – par Oct 27 '14 at 6:44
  • $\begingroup$ Oh you're absolutely right. I saw the question after the first edit and thought it was the original. $\endgroup$ – par Oct 27 '14 at 16:28

If $p$ and $q$ are primes larger than $2$, then they are odd. It follows that $pq+1$ is even and larger than $2$, so $pq+1$ is composite.


Another kind of hint: If you have no idea where to start in this kind of problems, you can always try some small values and try if you can see a pattern. $$ \begin{eqnarray*} 3 \cdot 3 + 1 &=& 10 \\ 3 \cdot 5 + 1 &=& 16 \\ 5 \cdot 5 + 1 &=& 26 \\ 3 \cdot 7 + 1 &=& 22 \\ 5 \cdot 7 + 1 &=& 36 \\ &\vdots& \end{eqnarray*} $$



Since $p,q > 2$ and the product of two odd numbers is odd then $pq + 1$ must be even.

  • 2
    $\begingroup$ A very strange use of "Since". The conclusion in the previous sentence was already proved. $\endgroup$ – Marc van Leeuwen Oct 27 '14 at 4:42

If $p,q>2$ and $p,q\in\Bbb P$ then $2\not\mid p,q$. This is obvious.

If $p,q$ are odd then $2\mid (p*q+1)$, what make obvious that is not prime.


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.