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

1. ## 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.

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.

2. ## 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

...