SUNY Geneseo Department of Mathematics
Monday, February 20
Math 239 01
Spring 2017
Prof. Doug Baldwin
My solution to problem set 4, in both PDF and LaTeX forms, is available under “Files” (specifically in the “Solutions” folder) in Canvas.
Proposition (Progress Check 3.16): for each integer n, if n ≡ 2 (mod 4) then n ≢ 3 (mod 6)
a ≡ b (mod n) means a = kn + b for some integer k, or in Sundstrom’s definition that n divides (a-b), i.e., a-b = kn for some integer k.
Prove the proposition. The proof is by contradiction. Assume the negation of the proposition, i.e., that there exists some integer n such that n ≡ 2 (mod 4) and n ≡ 3 (mod 6). Since n ≡ 2 (mod 4), n = 4k + 2 for some integer k. Note that 4k + 2 = 2(2k+1) which is even. Similarly, n ≡ 3 (mod 6) means n = 6j + 3 for some integer j; 6j + 3 = 6j + 3 + 1 - 1 = 6j + 2 + 1 = 2(3j + 1) + 1, which is odd. Thus n is both even and odd, which is impossible. Since the negation of the proposition is impossible, the proposition must be true. QED.
Or an alternate proof, picking up at the point where n = 4k + 2 = 6j + 3 for integers k and j. Since both definitions of n must be equal, we have
Since the integers are closed under multiplication and subtraction, the left side of this equation is an integer, but the right side is not. It is a contradiction to say that 2k - 3j is both an integer and not an integer, so we again conclude that the original proposition must be true. QED.
Both of these are good proofs. The point in a proof by contradiction is to reach some contradiction, there isn’t generally one “right” contradiction you need to find.
Who cares? This proof does more than prove that a particular number is irrational. It is most likely the first time you have actually seen a proof that any number is irrational, i.e., that irrational numbers exist at all.
Practice the ideas: prove that √6 is irrational. The proof is by contradiction, i.e., we assume that √6 is rational, and thus that there are integers x and y such that x/y = √6 and x and y have no common factors. Then x2/y2 = 6, or x2 = 6y2 = 2(3y2) which is even, and so x is also even, i.e., x = 2a for some integer a. Now we have
and so 2a2 = 3y2. This means 3y2 is even, and the only way for a product to be even is for at least one argument to be even. Since 3 is odd, y2 must even, which in turn means that y is even. But now x and y have a common factor 2, which contradicts the assumption that they have no common factors. We therefore conclude that the negation of the proposition is false, and so that √6 is in fact irrational.
Proofs in cases
Read section 3.4