Results 1 to 4 of 4

Math Help - proof

  1. #1
    Junior Member
    Joined
    Mar 2007
    Posts
    34

    proof

    If n is an integer that is NOT a multiple of 3, then n^2 = 1 mod 3

    I did ...

    to the contrary, if n is a multiple of 3 then n = 0 mod 3

    then n^2 is also a multiple of 3 -> n^2 = 0 mod3 reaching a contradition

    ---> <---- therefore n^2 = 1mod 3 when n is not a multiple of 3. QED.

    Is this correct?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by smoothi963 View Post
    If n is an integer that is NOT a multiple of 3, then n^2 = 1 mod 3

    I did ...

    to the contrary, if n is a multiple of 3 then n = 0 mod 3

    then n^2 is also a multiple of 3 -> n^2 = 0 mod3 reaching a contradition

    ---> <---- therefore n^2 = 1mod 3 when n is not a multiple of 3. QED.

    Is this correct?
    i'm afraid not. first of all, you made no assumption that n^2 was not 0 mod 3 so the contradiction doesn't really stand.

    note that you have an implication, that is, P => Q, you proved ~P=>~Q, which is not really a valid proof of P=>Q
    Follow Math Help Forum on Facebook and Google+

  3. #3
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by smoothi963 View Post
    If n is an integer that is NOT a multiple of 3, then n^2 = 1 mod 3

    I did ...

    to the contrary, if n is a multiple of 3 then n = 0 mod 3

    then n^2 is also a multiple of 3 -> n^2 = 0 mod3 reaching a contradition

    ---> <---- therefore n^2 = 1mod 3 when n is not a multiple of 3. QED.

    Is this correct?
    Try one of these:

    We show that if n is an integer that is NOT a multiple of 3, then n^2 = 1 mod 3.

    Proof:

    Assume n is not a multiple of 3, then we have two cases, n = 3k + 1 for some integer k, or n = 3m + 2 for some integer m.

    case 1: n = 3k + 1

    if n = 3k + 1, then n^2 - 1 = (3k + 1)^2 - 1 = 9k^2 + 6k + 1 - 1 = 9k^2 + 6k = 3(3k^2 + 2k).

    since 3k^2 + 2k is an integer, 3 | n^2 - 1. this means n^2 = 1 mod 3 ...note, 3 | n^2 - 1 means "3 divides n^2 - 1"

    case 2: n = 3m + 2

    if n = 3m + 2, then n^2 - 1 = (3m + 2)^2 - 1 = 9m^2 + 12m + 4 - 1 = 3(3m^2 + 4m + 1)

    since 3m^2 + 4m + 1 is an integer, 3 | n^2 - 1. this means n^2 = 1 mod 3

    so we see in both cases where n is not a multiple of 3, n^2 = 1 mod 3

    QED


    Alternate proof:

    Assume n is not a multiple of 3, then n = 1 mod 3 or n = 2 mod 3.

    case 1: n = 1 mod 3

    if n = 1 mod 3, then n^2 = 1^2 mod 3, so n^2 = 1 mod 3

    case 2: n = 2 mod 3

    if n = 2 mod 3, then n^2 = 2^2 mod 3, so n^2 = 4 mod 3, which is the same as saying n^2 = 1 mod 3 (do you know why?)

    so in both cases where n is not a multiple of 3, we have n^2 = 1 mod 3

    QED


    I'm sure that the first proof is valid, for the second, it depends on whether or not you can square both sides of a congruence modulus, which i think you can, but i'm not sure, i rarely work in modulus, i usually translate to algebra and manipulate and then translate back, similar to what i did in the first
    Follow Math Help Forum on Facebook and Google+

  4. #4
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    If you still insist on doing it by contradiction this is how:

    for an implication P=>Q, a proof by contradiction means we assume P is true and Q is false and show that a contradiction results. that is, we show

    (P and ~Q)=>C

    where C is a contradiction
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: October 19th 2010, 10:50 AM
  2. Replies: 0
    Last Post: June 29th 2010, 08:48 AM
  3. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 27th 2010, 10:07 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM
  5. proof that the proof that .999_ = 1 is not a proof (version)
    Posted in the Advanced Applied Math Forum
    Replies: 4
    Last Post: April 14th 2008, 04:07 PM

Search Tags


/mathhelpforum @mathhelpforum