Results 1 to 2 of 2

Math Help - prove by contradiction and contraposition, (a | b and ~( a | c) ) --> ~( a | b+c)

  1. #1
    Junior Member
    Joined
    Jul 2011
    Posts
    48

    prove by contradiction and contraposition, (a | b and ~( a | c) ) --> ~( a | b+c)

    For some reason I'm stuck on this.

    For proof by contraposition:

    For all integers a,b,c a | b+c --> ~(a | b) or (a | c).

    Suppose a | b+c

    b+c=a*k for some integer k

    ...

    I can't figure out exactly where to go from here.

    By contradiction:

    suppose there exists integers a,b,c such that a | b and ~( a | c) and a | b+c

    b+c=a*k for some integer k
    b=a*P for some integer P
    aP+c=ak
    p=(ak-c)/a
    p=k-c/a

    ?
    ...

    I feel like this should be really easy, but I can't seam to figure it out for the moment. Any help would be appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Jul 2011
    Posts
    48

    Re: prove by contradiction and contraposition, (a | b and ~( a | c) ) --> ~( a | b+

    Never mind it did turn out to be easy.

    it is sufficient to show that a | b+c and a | b --> a | c

    suppose a | b+c and a | b

    b+c=ak for some integer k
    b=ar for some integer r

    ar+c=ak
    c=ak-ar

    c=a(k-r)

    (k-r) is an integer by closure properties

    ...

    by contradiction

    b=ak for some integer k
    b+c=ar for some integer r
    ...
    c=a(r-k)
    ...
    a divides c contradicts ~(a divides c)
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Need help proving by contraposition
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 18th 2010, 10:25 PM
  2. Replies: 2
    Last Post: March 10th 2010, 03:29 PM
  3. Prove by contradiction
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: November 20th 2009, 11:26 AM
  4. Prove by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 20th 2009, 10:05 AM
  5. Prove by contradiction
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: November 13th 2009, 08:21 AM

Search Tags


/mathhelpforum @mathhelpforum