# Prove that $5n^2 - 3$ even $\implies n$ odd

I tried to prove this by contradiction. I used contradiction to show that if $n$ is odd then $5n^2 - 3$ is even; but my Professor said this is not a correct answer to the question: you need to prove that if $5n^2 - 3$ is even then $n$ is odd. Why is what I said wrong, and how do I fix it?

• Your error is in the direction of implication. "If $5n^2-3$ is even, then $n$ is odd" is not the same thing as "If $n$ is odd, then $5n^2-3$ is even." They both happen to be true, but they are not structurally equivalent. – Brian Tung Dec 14 '15 at 1:21
• Your prof probably would have accepted a proof that demonstrated that if $n$ is even then $5n^2+3$ is odd – WW1 Dec 14 '15 at 1:31

Suppose $5n^2-3=k$, where $k\in\mathbb{N}$ is even. Then $$5n^2=k+3$$ and we know that $k+3$ is odd. Next, we have $$n^2=\frac{k+3}{5}$$ which must be odd, because any odd divided by an odd is odd. Finally, we have that $$n=\sqrt{{\frac{k+3}{5}}}.$$ The square root of any odd perfect square must also be odd, so we know that $n$ is odd.

$$5n^2-3=2k+1$$

$$5n^2=2k+4$$

So $n^2$ must be even. So $n$ is even.

• The questoin has been edited. – user236182 Dec 14 '15 at 1:22

This is kinda soft, but you know that $x^2$, if x is odd positive, is always odd. You also know that odd times odd is also odd. And that odd +odd is even. Therefor you can almost deduce the answer.

$$5n^2-3\equiv 0 \pmod 2 \iff 5n^2\equiv3\pmod 2$$

As $$5\equiv 1, 3 \equiv 1 \pmod 2$$

We have that

$$5n^2\equiv 3 \pmod 2 \iff n^2 \equiv 1 \pmod 2$$

Suppose $n$ is even, that is $n\equiv 0\pmod 2$, then $n^2\equiv 0 \pmod 2$, thus $n$ is odd.

For contradiction, assume $n$ can be even. Let $n=2k$. Then $5n^2-3=2\left(10k^2-2\right)+1$ is odd, contradiction.

By contraposition, you can prove analogously that if $n$ is even, then $5n^2-3$ is odd.

You were asked to prove that if $5n^2-3$ is even, then n is odd. But what you proved was that if n is odd, then $5n^2-3$ is even.

$A \implies B$ is equivalent to $\neg B \implies \neg A$. So if you prove $\neg B \implies \neg A$, then you've proved $A \implies B$. This is an example of proof by contradiction. Assume the negation of the conclusion. Prove that this leads to a negation of one of your givens.

$A \implies B$ is NOT equivalent to $B\implies A$. For example $(x=2) \implies (x^2=4)$ is true. $(x^2=4) \implies x=2$ is false.

So for your question assume n is even, show that this means $5n^2-3$ is odd. Then you've done the right proof.

Suppose the question asked you to find out if this statement is true or false: "If $2n^2-3$ is odd then n is even". This statement is false because we can have n odd and $2n^2-3$ as odd. But if you assume n is even you will get $2n^2-3$ is odd. So your method would give the wrong result.

### Can be shown by a parity argument.

The lowest bit defines the oddness or evenness.

From $5n^2 - 3$ we can easily get the parity of the result as $(1.n_0.n_0)\oplus1$ which gives us $n_o\oplus1$

For the OP, $\oplus$ is the exclusive or operation.

Let the least significant bit of $n$ be $n_0$ ( = parity of $n$ ).

As an even $n$ will be $n_0=0$ the expression's parity is $0\oplus1=1$, which is odd. And of course an odd $n$ will get an even parity.

### Can be shown by simple substitution

Another method is simply to try $n = 2k$ and $n = 2k+1$ for an even and odd $n$ respectively.

For $n = 2k$ we get $5n^2-3 = 5(4k^2)-3$ which is always odd.

For $n = 2k+1$ we get $5n^2-3 = 5(4k^2)+5(4k)+5(1)-3$ which is always even.

To prove IF P THEN Q by contradiction you have to prove IF NOT Q and P THEN impossible.

Assume $5n^2 - 3$ is even and $n$ is even. If $5n^2 - 3$ is even then $5n^2$ is odd. If $n$ is odd then $n^2$ is odd. So $5*n^2 = 5*\text{ an odd number} = 5n^2 = \text {an even number}$. That's a contradiction. So if $5n^2 - 3$ is even th3n $n$ also even is impossible. So n is odd.

One type of proof by contradiction is a proof by contrapositive. To prove IF P THEN Q. You can prove IF NOT Q THEN NOT P (thus the only way P can be true is if Q is also.) (The contradiction is NOT P and P can't both be true.)

A proof by contrapositivve:

Suppose $n$ is even. Then $5n^2$ is even. So $5n^2 - 3$ is odd. So if $5n^2 -3$ is even, it must be $n$ is odd.

[A third of proof is a direct proof: If $5n^2 - 3$ is even then $5n^2$ is odd. So $n^2$ is odd. So $n$ is odd.]

What you tried to do was

IF Q THEN P. If $n$ is odd then $5n^2 -3$ is even. In this case that happens to be true but it isn't what was meant to be proven.

Consider IF p is a prime > 2 THEN p is odd. You can not prove IF p is odd greater than 2 THEN p is prime. That just isn't true. And it's not a contradiction nor a contrapositive.

That was what your professor objected to, not that you attempted a proof by contradiction.

As it turns out $n$ is odd $\iff 5n^2 - 3$ is even. You tried to prove $n$ odd $\implies 5n^2 - 3$ even. But the exercise was to prove $5n^2 - 3$ even $\implies n$ odd.

• Regarding the first paragraph: that's the contrapositive method. When you prove something by contradiction, you can get a contradiction anywhere, not only when "not P". – user236182 Dec 14 '15 at 1:31
• True. Careless error on my part. – fleablood Dec 14 '15 at 1:33
• To be honest I've been incorrectly including "contrapositive" as a type of proof by contradiction all my life. It's never gotten my into trouble as both are valid methods of proof. (The "contradiction" of a contrapositive is that the premise, which is not used, is proven to be false so if we assume it was always true then we have a contradiction.) But it's incorrect terminology and I shouldn't do it. – fleablood Dec 14 '15 at 1:53
• Well, contrapositive is a type of proof by contradiction. Every contrapositve type proof is a proof by contradiction. But not every proof by contradiction is a contrapositive proof. – Ameet Sharma Dec 14 '15 at 1:59
• Okay, I personally never use the term "proof by contrapositive" but then I'm not a teacher. Terminology mustn't be abused. – fleablood Dec 14 '15 at 2:04