Results 1 to 8 of 8

Math Help - Proving divisibility question using contradiction

  1. #1
    Newbie
    Joined
    Jan 2009
    Posts
    19

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    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)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2009
    Posts
    19
    yeah i did, still can't figure it out
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Mar 2009
    Posts
    90
    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.)
    Last edited by bmp05; March 27th 2009 at 10:14 AM. Reason: Oops.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    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 )
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Mar 2009
    Posts
    90
    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)......?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570

    Proof by contradiction

    Hello everyone
    Quote Originally Posted by bmp05 View Post
    ...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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proving zero vector is unique - by contradiction?
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: March 10th 2011, 05:13 AM
  2. [SOLVED] Proving a number is irrational by contradiction
    Posted in the Algebra Forum
    Replies: 4
    Last Post: February 5th 2011, 02:09 AM
  3. Proving divisibility
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: May 11th 2010, 09:00 AM
  4. [SOLVED] Proving a theorem without using contradiction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 16th 2009, 03:42 PM
  5. proving √q is irrational by contradiction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 18th 2008, 06:31 PM

Search Tags


/mathhelpforum @mathhelpforum