Results 1 to 8 of 8

Math Help - [SOLVED] discrete math help

  1. #1
    Newbie
    Joined
    Feb 2009
    Posts
    3

    [SOLVED] discrete math help

    hey I understand how to do a proof by contradiction but i dont know where to start with this question, Use proof by contradiction to show that for all integers n, if n2 is divisible by 3 then n is divisible by
    3.


    thank you very much
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Jan 2009
    Posts
    94
    I think you meant n^2 with n2.

    For contradiction, start with the opposide of the claim:

    Let there be an integer n such that n^2 is divisible by 3 WHILE n itself is not divisible by 3.

    Then do something about it
    Sorry I got to go...
    I'll check later...

    -O
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Flow Master
    mr fantastic's Avatar
    Joined
    Dec 2007
    From
    Zeitgeist
    Posts
    16,948
    Thanks
    5
    Quote Originally Posted by oswaldo View Post
    I think you meant n^2 with n2.

    For contradiction, start with the opposide of the claim:

    Let there be an integer n such that n^2 is divisible by 3 WHILE n itself is not divisible by 3.

    Then do something about it
    Sorry I got to go...
    I'll check later...

    -O
    The "something about it" would be to consider the prime factor decomposition of n and hence of n^2 ....
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Feb 2009
    Posts
    3
    i understand prime factor decomposition sort of, but i dont understand how to implement it. but thanks for the help so far
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,610
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by last_chance View Post
    i understand prime factor decomposition sort of, but i dont understand how to implement it. but thanks for the help so far
    Look at some examples.
    n = 2^3  \cdot 3^2  \cdot 5\, \Rightarrow \,n^2  = 2^6  \cdot 3^4  \cdot 5^2, n squared must have a factor of 3.

    n = 2^3  \cdot 7^2  \cdot 11\, \Rightarrow \,n^2  = 2^6  \cdot 7^4  \cdot 11^2, n squared cannot have a factor of 3.

    Does that help?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Jan 2009
    Posts
    94
    Let there be an integer n such that n^2 is divisible by 3 WHILE n itself is not divisible by 3.

    n^2 = 3k, where k is an integer
    n^2 - 1 = 3k-1, now (3k-1) is not divisible by 3, right?
    (n-1)(n+1) = 3k-1
    Then we can say:
    (n-1) is NOT divisible by 3 AND (n+1) is NOT divisible by 3.
    means n is divisible by 3. (*)
    => CONTRADICTION.

    (*) Exactly "one" of three consecutive integers is divisible by 3

    -O
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Feb 2009
    Posts
    3
    yah thats what i figured it does clear it up alot thanks. but how do you know that first one is clearly a factor of 3?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Jan 2009
    Posts
    94
    If you are asking: "why n^2 is divisible by 3" That's our assumption. Starting point.

    If you are asking why (n-1) and (n+1) is not divisible by 3? The reason: (n-1)*(n+1) is not divisible by 3. If the result of an integer multiplication is not divisible by 3, then none of its components is divisible by 3.

    Finally, (n-1), n, (n+1) are consecutive. One MUST be divisible by 3.

    -O
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Using Product Rule for Discrete Math
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 5th 2009, 06:23 AM
  2. [SOLVED] Discrete Math Proof: Combinations
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 24th 2009, 05:46 PM
  3. [SOLVED] discrete math help for B union E
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: February 6th 2009, 07:30 AM
  4. Help me, I am new to discrete math
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: January 25th 2008, 05:15 PM
  5. Discrete Math
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 26th 2007, 05:30 PM

Search Tags


/mathhelpforum @mathhelpforum