Question

2. (a) Use a prove by contradiction to show that if a and b are nonzero integers such that a divides b and a + b is odd, then a is odd. (b) Prove that if n is a positive integer, then n² does not equal 2(mod 4).

Answer 1

a. Assume a is even, so a = 2k for some integer k. Now let a and b be integers such that a divides b and a + b is odd.

Since a divides b, b = an for integer n, and in turn b = 2nk, which means b is even and hence a + b is also even. But this contradicts our initial assumption, so a must be odd.

b. Let n be even, so that n = 2k for some integer k. Then

n² = (2k)² = 4k²

so that n² ≡ 0 (mod 4).

Now let n be odd, so n = 2k + 1 for integer k. Then

n² = (2k + 1)² = 4k² + 4k + 1

so that n² ≡ 1 (mod 4).

Therefore n² is never congruent to 2 (mod 4).