# Proving divisibility question using contradiction

• Mar 24th 2009, 03:45 AM
thecleric
Question:
For any integer n, (n^2 - 2) is not divisible by 4 ... Prove by contradiction

Proof: Suppose the contrary, that is for any integer m, (m^2 - 2) is divisible by 4. By definition of divide, n = dk. Thus (m^2 - 2) = 4k.

i don't know how to finish this. i know that if n squared is even then n is even (long way is n=2k for even, n=2k+1 for odd) and n has to be even and greater than 2 for my thus statement to be true. just can't quite piece it together.
• Mar 24th 2009, 04:38 AM
clic-clac
Hi

Take care: the contrary of "for any integer $n,\ (n^2-2)$ isn't divisible by $4$" is "There exists an integer $m$ such that $4|(m^2-2)$"

What can we say about $m^2-2$ modulo $4$ ? (Check the two cases: $m$ is odd / $m$ is even)
• Mar 24th 2009, 09:57 AM
thecleric
yeah i did, still can't figure it out
• Mar 24th 2009, 11:52 AM
clic-clac
For instance if $m$ is even there is an integer $k$ such that $m=2k$ then $m^2=4k^2\equiv 0\ \text{mod}4$ therefore $m^2-2\equiv2\ \text{mod}4$ i.e. $m^2-2$ isn't divisible by 4.

Do the same for $m$ odd and you'll have that "exists $m$ s.t. $4|(m^2-2)$" leads to a contradiction.
• Mar 27th 2009, 10:53 AM
bmp05
I'm studying this topic as well and I need some help with the proofs:
So, first we assume that $\forall n \in N, P(n)=4 \mid (n^2-2)$ is false
$\Rightarrow \exists n \in N, 4 \mid (n^2 -2)$
$\Rightarrow \exists i \in N: i= \frac{(n^2-2)}{4}=\frac{n^2}{4} - \frac{1}{2}$
...and this is where you need the modulo thing, I guess, because you need the term $\frac{n^2}{4}$ to have a remainder of two for i to be solvable. For example $n^2 = 2, 18$ but I don't know how to prove this. It would be good to see a finished proof! Can someone write the proof in the correct way as well, because I need to learn how to write a proof correctly. Actually, that sounds a little bit rude- but I'd like to be able to use the symbols correctly etc. and any help would be much appreciated!
(These math symbols take some getting used to.)
• Mar 27th 2009, 12:49 PM
clic-clac
Hi

The modulo thing allows you to write very correctly what you want to say, i.e. for any integer, the remainder of the division of $n^2$ by 4 is never 2.

So you've assumed the contrary, which is, under a "modular form":

$n^2\equiv 2\ \text{mod}4$

Since for any integer $m,\ m\equiv 0,1,2\ \text{or}\ 3\ \text{mod}4,$ a way to prove the statement is to compute $0^2, 1^2, 2^2, 3^2$ and see that it only can be $0$ or $1\ \text{mod}4.$
Therefore no square can be congruent to 2 modulo 4. ( because $n\equiv a\ \text{mod}4\Rightarrow n^2\equiv a^2\ \text{mod}4$ )
• Mar 27th 2009, 01:44 PM
bmp05
does that mean you need a Lemma? This is a formal question about how you would present or show the results of the "modular form." "Modulo" is similar to the 'mod' [and 'div'] from programming? How would you prove the mod 4 pattern for all n? (it seems clear that it is 1, 0, 1 ...), $2^2 = 4, 4^2 = (2^2).(2^2), 6^2 = (2^2).(3^2), 8^2 = (2^2).(4^2)...$...?
• Mar 28th 2009, 12:00 AM
Hello everyone
Quote:

Originally Posted by bmp05
...It would be good to see a finished proof! Can someone write the proof in the correct way as well, because I need to learn how to write a proof correctly. Actually, that sounds a little bit rude- but I'd like to be able to use the symbols correctly etc. and any help would be much appreciated!
(These math symbols take some getting used to.)

clic-clac has given you all that you need for the proof. You can use the mod notation to devise a direct proof, but if a proof by contradiction is required, I would set it out formally as follows.

To prove

$n^2 -2$ is not divisible by 4 $\forall n \in \mathbb{N}$

Proof

Assume the contrary, namely, $\exists n \in \mathbb{N}, 4|(n^2 -2)$

Then for this value of $n, \exists p \in \mathbb{N}, n^2 - 2 = 4p$

$\Rightarrow n^2 = 4p+2 = 2(2p+1)$

$\Rightarrow n^2$ is even $\Rightarrow n$ is even

$\Rightarrow \exists q \in \mathbb{N}, n = 2q$

$\Rightarrow n^2 = 4q^2$

$\Rightarrow 4|n^2$

This contradicts the assumption that $4|(n^2 - 2)$.

Therefore $\neg \,\exists n \in \mathbb{N}, 4|(n^2-2)$