4
$\begingroup$

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?

$\endgroup$
1
  • 14
    $\begingroup$ It is even, since $p,q>2$. $\endgroup$ Commented Oct 26, 2014 at 13:50

5 Answers 5

39
$\begingroup$

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.

$\endgroup$
0
11
$\begingroup$

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*} $$

$\endgroup$
10
$\begingroup$

Hint:

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

$\endgroup$
1
  • 2
    $\begingroup$ A very strange use of "Since". The conclusion in the previous sentence was already proved. $\endgroup$ Commented Oct 27, 2014 at 4:42
9
$\begingroup$

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".)

$\endgroup$
4
  • 7
    $\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
    Commented Oct 27, 2014 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$ Commented Oct 27, 2014 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
    Commented Oct 27, 2014 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
    Commented Oct 27, 2014 at 16:28
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .