Proving divisibility question using contradiction

Printable View

March 24th 2009, 02:45 AM
thecleric

Proving divisibility question using contradiction

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.
March 24th 2009, 03: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)
March 24th 2009, 08:57 AM
thecleric

yeah i did, still can't figure it out
March 24th 2009, 10: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.
March 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 $\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.)
March 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 $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$ )
March 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 ...), $2^2 = 4, 4^2 = (2^2).(2^2), 6^2 = (2^2).(3^2), 8^2 = (2^2).(4^2)...$ ...?
March 27th 2009, 11:00 PM
Grandad

Proof by contradiction

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)$

Grandad