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?
$\begingroup$
$\endgroup$
1
-
14$\begingroup$ It is even, since $p,q>2$. $\endgroup$– Eclipse SunOct 26, 2014 at 13:50
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
0
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.
answered Oct 26, 2014 at 13:50
$\begingroup$
$\endgroup$
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*} $$
$\begingroup$
$\endgroup$
1
Hint:
Since $p,q > 2$ and the product of two odd numbers is odd then $pq + 1$ must be even.
answered Oct 26, 2014 at 13:50
-
2$\begingroup$ A very strange use of "Since". The conclusion in the previous sentence was already proved. $\endgroup$ Oct 27, 2014 at 4:42
$\begingroup$
$\endgroup$
4
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".)
answered Oct 27, 2014 at 4:53
-
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$– parOct 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$ 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$– parOct 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$– parOct 27, 2014 at 16:28
$\begingroup$
$\endgroup$
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.
answered Oct 27, 2014 at 16:37