**Definitions.**

- An integer x is called
**even**(respectively**odd**) if there is another integer k for which x = 2k (respectively 2k+1). - Two integers are said to have the same
**parity**if they are both odd or both even.

** Theorem.** If x and y are two integers for which x+y is even, then x and y have the same parity.

**Proof.** The contrapositive version of this theorem is "If x and y are two integers with opposite parity, then their sum must be odd." So we assume x and y have opposite parity. Since one of these integers is even and the other odd, there is no loss of generality to suppose x is even and y is odd. Thus, there are integers k and m for which x = 2k and y = 2m+1. Now then, we compute the sum x+y = 2k + 2m + 1 = 2(k+m) + 1, which is an odd integer by definition.

q

- Method of Contradiction: Assume P and Not Q and prove some sort of contradiction.
- Method of Contrapositive: Assume Not Q and prove Not P.

The second idea is the remainder and modular arithmetic. For two integers m and n, **n mod(m) = r** will be the remainder resulting when we divide m into n. This means that there is an integer q such that n = mq + r. For example, 127 mod(29) = 11 since 29 will go into 127 4 times with a remainder of 11 (or, in other words, 127 = (4)(29) + 11). Determining whether or not a positve integer is a perfect square might be difficult. For example, is 82,642,834,671 a perfect square? First we compute 82,642,834,671 mod(4) = 3. Then use this theorem:

**Theorem.** If n is a positive integer such that n mod(4) is 2 or 3, then n is not a perfect square.

**Proof.** We will prove the contrapositive version: "If n is a perfect square then n mod(4) must be 0 or 1." (Do you understand why this is the contrapositive version?) Suppose n = k^{2}. There are four cases to consider.

- If k mod(4) = 0, then k = 4q, for some integer q. Then, n = k
^{2}= 16 q^{2}= 4(4 q^{2}) , i.e. n mod(4) = 0. - If k mod(4) = 1, then k = 4q + 1, for some integer q. Then, n = k
^{2}= 16 q^{2}+ 8 q + 1= 4(4 q^{2}+ 2 q) + 1, i.e. n mod(4) = 1. - If k mod(4) = 2, then k = 4q + 2, for some integer q. Then, n = k
^{2}= 16 q^{2}+ 16 q + 4 = 4(4 q^{2}+ 4 q + 1), i.e. n mod(4) = 0. - If k mod(4) = 3, then k = 4q + 3, for some integer q. Then, n = k
^{2}= 16 q^{2}+ 24 q + 9 = 4(4 q^{2}+ 6 q + 2) + 1, i.e. n mod(4) = 1.

q

- If x and y are two integers whose product is even, then at least one of the two must be even.
- If x and y are two integers whose product is odd, then both must be odd.
- If n is a positive integer such that n mod(3) = 2, then n is not a perfect square.
- If a and b a real numbers such that the product a b is an irrational number, then either a or b must be an irration number.

** Next==>**If, and Only If

**<==Back To **Proof by Contradiction