• Mar 24th 2009, 02: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, 03:38 AM
clic-clac
Hi

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

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

Do the same for $\displaystyle m$ odd and you'll have that "exists $\displaystyle m$ s.t. $\displaystyle 4|(m^2-2)$" leads to a contradiction.
• Mar 27th 2009, 09:53 AM
bmp05
I'm studying this topic as well and I need some help with the proofs:
So, first we assume that $\displaystyle \forall n \in N, P(n)=4 \mid (n^2-2)$ is false
$\displaystyle \Rightarrow \exists n \in N, 4 \mid (n^2 -2)$
$\displaystyle \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 $\displaystyle \frac{n^2}{4}$ to have a remainder of two for i to be solvable. For example $\displaystyle 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, 11:49 AM
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 $\displaystyle n^2$ by 4 is never 2.

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

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

Since for any integer $\displaystyle m,\ m\equiv 0,1,2\ \text{or}\ 3\ \text{mod}4,$ a way to prove the statement is to compute $\displaystyle 0^2, 1^2, 2^2, 3^2$ and see that it only can be $\displaystyle 0$ or $\displaystyle 1\ \text{mod}4.$
Therefore no square can be congruent to 2 modulo 4. ( because $\displaystyle n\equiv a\ \text{mod}4\Rightarrow n^2\equiv a^2\ \text{mod}4$ )
• Mar 27th 2009, 12: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 ...), $\displaystyle 2^2 = 4, 4^2 = (2^2).(2^2), 6^2 = (2^2).(3^2), 8^2 = (2^2).(4^2)...$...?
• Mar 27th 2009, 11:00 PM
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

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

Proof

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

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

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

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

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

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

$\displaystyle \Rightarrow 4|n^2$

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

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