If, and Only If

If, and Only If

Many theorems are stated in the form "P, if, and only if, Q". Another way to say the same things is: "Q is necessary, and sufficient for P". This means two things: "If P, Then Q" and "If Q, Then P". So to prove an "If, and Only If" theorem, you must prove two implications.

Example: Division

In this example we will use a very useful fact about integers, the so called Division Algorithm: If n and m are integers, then there are two other integers q and r, where 0 <= r < m, and such that n = qm + r. For example, if n = 103 and m = 15, then 103 = (6)(15) + 13. (That is, if we divide15 into 103, we get a quotient of q = 6, with a remainder of r = 13.)

Theorem. If a is an integer, then a is not evenly divisible by 3 if, and only if, a2 -1 is evenly divisble by 3.

Proof. Since this is an "If, and Only If" theorem, we must prove two implications.

("If") We must prove "a is not evenly divisible by 3 if a2 -1 is evenly divisble by 3". So we assume that 3 evenly divides a2 -1 = (a-1)(a+1). Since 3 is a prime number, 3 must evenly divide either a-1 or a+1. In either case, it should be apparent that 3 cannot evenly divide a.

("Only If"). We must prove "a is not evenly divisible by 3 only if a2 -1 is evenly divisble by 3." This means "If a is not evenly divisible by 3, then a2 -1 is evenly divisble by 3". This is where we use the division algorithm stated above. We can write a = 3q + r, where r = 0, 1 or 2. Our assumption that a is not divisible by 3 implies r cannot be 0. If r =1, then a-1 = 3q and so 3 evenly divides a2 -1 = (a-1)(a+1). A similar argument works if r = 2.

q
Sometimes you can prove an "If, and Only If" assertion without explicitly dividng the proof into two parts. The next example illustrates how this might be done.

Example: A Division Rule

You probably learned in school that a positive integer n is evenly divisble by 3 if the sum of the digits of n is divisble by 3. For example, 2620461 is evenly divisble by 3 since 2 + 6 + 2 + 0 + 4 + 6 + 1 = 21 = (3)(7). In fact, 2620461 = (3)(873487). This condition is realy necessary and sufficient.

Theorem. A postive integer n is evenly divisible by 3 if, and only if, the sum of the digits of n is divisble by 3.

Proof. Suppose n is a positve integer whose digit representation is a0a1...ak. This means, n = a0 + a1 10 + ...ak 10k. The digit sum is s = a0 + a1 + ... + ak.

Now, n -s = (a0 + a1 10 + ...ak 10k) - (a0 + a1 + ... + ak) = a1 9 + a2 99 + ... + ak (99...9) (where the last term has k nines). So, clearly, n - s is divisble by 3. It follows that n is divisible by 3 if, and only if, s is divisble by 3.

q

Exercises

Prove each of the following.

1. If a is an integer, then a is not evenly divisible by 5 if, and only if, a4 -1 is evenly divisble by 5.

2. For two integers a and b, a+b is odd if, and only if, exactly one of the integers, a or b, is odd.

3. For two integers a and b, the product ab is even if and only if at least one of the integers, a or b, is even.

4. A postive integer n is evenly divisible by 9 if, and only if, the sum of the digits of n is divisble by 9.

5. A postive integer n is evenly divisible by 11 if, and only if, the difference of the sums of the digits in the even and odd positions in n is divisible by 11.

<==Back To Proof by Contrapositive