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, a^{2} -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 a^{2} -1 is evenly divisble by 3". So we assume that 3 evenly divides a^{2} -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 a^{2} -1 is evenly divisble by 3." This means "If a is not evenly divisible by 3, then a^{2} -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 a^{2} -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 a_{0}a_{1}...a_{k}. This means, n = a_{0} + a_{1} 10 + ...a_{k} 10^{k}. The digit sum is s = a_{0} + a_{1} + ... + a_{k}.

Now, n -s = (a_{0} + a_{1} 10 + ...a_{k} 10^{k}) - (a_{0} + a_{1} + ... + a_{k}) = a_{1} 9 + a_{2} 99 + ... + a_{k} (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.
- If a is an integer, then a is not evenly divisible by 5 if, and only if, a
^{4} -1 is evenly divisble by 5.
- For two integers a and b, a+b is odd if, and only if, exactly one of the integers, a or b, is odd.
- 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.
- A postive integer n is evenly divisible by 9 if, and only if, the sum of the digits of n is divisble by 9.
- 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.

** Next==>**Proof by Mathemaitcal Induction

**<==Back To **Proof by Contrapositive

Back to Proofs