Discrete math: proving by contradiction. . .

Question

Prove by contradiction: If an integer n has the form 3K+1, then it does not have the form 9L+5.

Answer 1

Assume it does have the form 9L + 5.  Then

 

3K + 1 = 9L + 5

 

3K + 1 = (9L + 4) + 1

 

3K = 9L + 4

 

K = (9L + 4)/3 = 3L + 4/3

 

K = 3L + 4/3 ⇒ K ≠ an integer.  Here is your contradiction, since K and L are assumed to be integers.

 

Therefore, 3K + 1 ≠ 9L + 5