7
$\begingroup$

I tried to prove that $n^2 - 2$ is not divisible by 4 via proof by contradiction. Does this look right?

Suppose $n^2 - 2$ is divisible by $4$. Then:

$n^2 - 2 = 4g$, $g \in \mathbb{Z}$.
$n^2 = 4g + 2$.

Consider the case where $n$ is even.

$(2x)^2 = 4g + 2$, $x \in \mathbb{Z}$.

$4x^2 = 4g + 2$.

$4s = 4g + 2$, $s = x^2, s \in \mathbb{Z}$ as integers are closed under multiplication.

$2s = 2g + 1$

$2s$ is even, and $2g + 1$ is odd (by definition of even/odd numbers). An even number cannot equal an odd number, so we have a contradiction.

Consider the case where $n$ is odd.

$(2x + 1)^2 = 4g + 2$, $x \in \mathbb{Z}$

$4x^2 + 4x + 1 = 4g + 2$

$4x^2 + 4x = 4g + 1$

$4(x^2 + x) = 4g + 1$

$4j = 4g + 1$, $j = x^2 + x, j \in \mathbb{Z}$ as integers are closed under addition

$2d = 2e + 1$, $d = 2j, e = 2g; d, e \in \mathbb{Z}$ as integers are closed under multiplication

$2d$ is even, and $2e + 1$ is odd (by definition of even/odd numbers). An even number cannot equal an odd number, so we have a contradiction.

As both cases have a contradiction, the original supposition is false, and $n^2 - 2$ is not divisible by $4$.

$\endgroup$
  • 4
    $\begingroup$ You could simplify your proof slightly. In the first case, you could go from $4x^2 = 4g + 2$ to $4(x^2-g) = 2$. This would imply that $4$ divides $2$ which is a contradiction. Similarly, in the second case, you could go from $4(x^2+x) = 4g + 1$ to $4(x^2+x-g) = 1$ so that $4$ divides $1$ which is also a contradiction. $\endgroup$ – Cameron Williams Mar 13 '17 at 16:30
6
$\begingroup$

Your proof is perfect.

We can shorten your proof by for example going from $4x^2=4g+2$ (in case 1) to saying "The left-hand side has remainder $0$ after division by $4$, yet the right side has remainder $2$; this is impossible" (basically, looking at the expression $\mod 4$ instead of dividing by $2$ and looking $\mod 2$).

Also, the second case was trivially impossible, since $n^2=4g+2$ has no solutions if $n$ is odd (since then $n^2$ is odd, but $4g+2$ is even).

Depending on the context (what you know, what you can use, etc), steps like $x^2+x=j$ with the remark that integers are closed under addition and multiplication are mostly considered so trivial that it's not worth mentioning. I repeat however that this is completely dependent on context, and if you want to make sure your audience is aware of these facts and/or steps, you should mention them. More detailed explanations with steps rarely hurt the proof.


The proof can be done a lot quicker however (without contradiction) by looking $\mod 4$. It is quite easy to prove that squares are either $0$ or $1\mod 4$, so $n^2-2$ is either $-2$ or $-1\mod 4$, and thus, $n^2-2$ cannot be divisible by $4$.

$\endgroup$
2
$\begingroup$

For odd $n$, $n^2-2$ is odd.

For even $n$, $n^2$ is divisible by $4$, so that $n^2-2$ is not.


By contradiction:

Let $n$ be odd. Then $n^2-2$ is both odd and a multiple of four.

Let $n$ be even. Then $n^2-2$ and $n^2$ are both multiples of $4$, so that $2$ is a multiple of $4$.

$\endgroup$
  • 2
    $\begingroup$ This is not a proof by contradiction though $\endgroup$ – vrugtehagel Mar 13 '17 at 16:24
  • $\begingroup$ @vrugtehagel why do you need a proof by contradiction? $\endgroup$ – mez Mar 13 '17 at 16:26
  • 2
    $\begingroup$ @mez, that's what the OP is asking. $\endgroup$ – vrugtehagel Mar 13 '17 at 16:27
  • 2
    $\begingroup$ @BrianTung obviously, you can transform it into the standard not-really-proof-by-contradiction by assuming the statement is true, then proving that it's false directly, and then stating that the assumption was false. Don't get me wrong; I like the elegance and simplicity of this proof, I just don't think that it's what the OP was looking for. $\endgroup$ – vrugtehagel Mar 13 '17 at 16:32
  • 2
    $\begingroup$ The question doesn't clearly state that proof by contradiction IS required, just that he did try this as a technique $\endgroup$ – Cato Mar 13 '17 at 16:39
0
$\begingroup$

Assume $4 \mid n^2-2$, for $n \in \mathbb{z}$. This means we can rewrite $n^2-2$ as $4k$, which implies $n^2=2(2k+1)$. This is clearly impossible; this implies $4 \nmid n^2$ but $2 \mid n^2$. So our initial assumption is wrong.

$\endgroup$
0
$\begingroup$

Anohter Idea of proof goes as follows:

First of all we need to know that any square of integer is either of the form 4k or 4k+1.

Suppose, to the contrary, that 4 divides $n^2-2$, then: $$4k = n^2-2$$ $$4k+2 = n^2$$ A contradiction. Thus $n^2-2$ cannot be divisible by 4.

$\endgroup$

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.