6

$f(x)=2x+1$ produces a prime number if and only if x is prime, how can we prove this false?

I know this isn't very math-proofy, but can't we just plug in a number we know that is prime, i.e. $x=7$, and observe $f(7)=15$, which is not prime?

I'm intersting in writing a math proof for this, but I'm not exactly sure if my "proof" is good enough/proper. How should I do this?

Jason
  • 3,563
  • Even each of the implications is false. – Did Dec 26 '14 at 22:50
  • 1
    That is enough to disprove the if and only if assertion, and it is mathy enough. Note that the other direction can also be disproved, for $19$ is prime but $9$ is not. – André Nicolas Dec 26 '14 at 22:53
  • Let $p(x)$ be the proposition "$x$" is prime. Your statement is equivalent to writing: $\forall x: p(x)\leftrightarrow p(2x+1)$. To disprove it, show that $\exists x:(p(x)\wedge \neg p(2x+1))\vee (\neg p(x)\wedge p(2x+1))$, which is precisely what you have done. – Edward Jiang Dec 26 '14 at 22:53
  • I believe that 6 -> 13 is the lowest counterexample (unless you count 1 -> 3, since 1 is not prime). – Scott - Слава Україні Dec 26 '14 at 22:59

3 Answers3

8

To prove a statement false, all you ever need to do is exhibit a counterexample. Your counterexample $x=7$ demonstrates that (one implication direction of) the proposition is not true for some $x$, and hence it can never be true for every $x$. So yes, your proof is perfectly "math-proofy" enough.

theage
  • 3,677
3

Your counterexample proves that $2x+1$ need not be prime if $x$ is prime. That is the "if" part, and your counterexample contradicts it, and hence the whole statement.

You might want also to note that $2\cdot 6 +1=13$ is a counterexample to the "only if" part - in that $f(x)$ can be prime even if $x$ is not.

Mark Bennet
  • 100,194
1

Let $\mathbb{P}$ denote the set of prime numbers.

We need to prove logical statement $A$:

$\neg\forall{x\in\mathbb{N}}:{2x+1}\in\mathbb{P}\iff{x}\in\mathbb{P}$

Or the equivalent logical statement $B$:

$\neg\forall{x\in\mathbb{N}}:({2x+1}\in\mathbb{P}\implies{x}\in\mathbb{P})\wedge({x}\in\mathbb{P}\implies{2x+1}\in\mathbb{P})$

Or the equivalent logical statement $C$:

$\exists{x\in\mathbb{N}}:\neg({2x+1}\in\mathbb{P}\implies{x}\in\mathbb{P})\vee\neg({x}\in\mathbb{P}\implies{2x+1}\in\mathbb{P})$

Or the equivalent logical statement $D$:

$\exists{x\in\mathbb{N}}:\neg[({2x+1}\not\in\mathbb{P})\vee({x}\in\mathbb{P})]\vee\neg[({x}\not\in\mathbb{P})\vee({2x+1}\in\mathbb{P})]$

Or the equivalent logical statement $E$:

$\exists{x\in\mathbb{N}}:[({2x+1}\in\mathbb{P})\wedge({x}\not\in\mathbb{P})]\vee[({x}\in\mathbb{P})\wedge({2x+1}\not\in\mathbb{P})]$

Finally, in order to prove $\exists{x}$, we only need to find such value of $x$:

$x=6\implies(2x+1\in\mathbb{P})\wedge(x\not\in\mathbb{P})\implies{E}\iff{D}\iff{C}\iff{B}\iff{A}$

barak manos
  • 43,109
  • It is quite useless to overload things with symbols! – Pedro Dec 29 '14 at 18:41
  • @PedroTamaroff: Thank you for the constructive comment. OP wrote "I'm interested in writing a math proof for this, but I'm not exactly sure if my proof is good enough/proper", so I wrote down the proof as "mathematically" as possible. Obviously, the question itself is easy to answer in a more "natural" way (several ways as a matter of fact), and OP appears to be well aware of that, but he or she is asking for a formal proof. So I answered accordingly. – barak manos Dec 29 '14 at 18:53
  • I cannot find where the OP asks for a "formal" proof. One shouldn't confuse formality with rigour. One can be perfectly rigorous without being formal. Being formal is usually much more tortuous and sometimes less useful and iluminating than being rigorous. In particular, saying "$9$ is not prime, but $19=2\cdot 9+1$ is, and $7$ is prime, but $15=2\cdot 7+1$ isn't" is a perfectly valid and rigorous proof that neither $x$ being prime implies $2x+1$ being prime, nor $2x+1$ being prime implies $x$ being prime. – Pedro Dec 29 '14 at 18:57