Taxonomy of proof: counterexample

IT MAY BE SIGNIFICANTLY EASIER to disprove something than to prove it, for to prove a theorem false, often all you need to do is provide a counterexample. ``Disproofs'' can be as simple as this:

Theorem(?) 6   All prime numbers are odd.

Disproof: Two is prime, but two is even.

Usually, however, counterexamples are not that easy to come by. Frequently, you are not asked to disprove something, but are given a statement and told to either prove or disprove it. A good general strategy in such cases is to search for a proof, but use any weaknesses in your proof strategy to search for counterexamples. Here is an example of this technique. The definition we need here is this: $a \bmod b$ is defined to be the unique integer $r$ such that, for some $q$, $bq + r = a$, $bq \leq a$, and $b(q+1) > a$ . That is, $a \bmod b$ is the remainder when $a$ is divided by $b$. Note that from the definition it follows that $0 \leq a \bmod b < b$.

Theorem(?) 7   Prove or disprove: There is no pair of numbers $a$ and $b$ such that $a \bmod b = b \bmod a$.

When asked to do things with pairs of objects, it is often possible to simplify the relationship between the two numbers to help with the proof. In this case, we can assume $a < b$ without loss of generality, because if $a > b$, we can swap $a$ and $b$ and get the same equation -- we are taking advantage of the problem's symmetry. We must be careful not to forget the third case, however, that $a = b$. This turns out to be the chink in our proof that leads to a counterexample, but for right now let's plow ahead regardless.

First assume $a < b$. Then $a \bmod b = a$ (from the definition above, with $q = 0$ and $r = a$). But $b \bmod a < a$, from our observation above that $x \bmod y$ is always less than $y$. Hence $a \bmod b \not= b \bmod a$ for any values of $a$ or $b$. By switching around $a$ and $b$, we get a similar proof for the case $b < a$.

But now we try to prove the theorem for the case $a = b$. And here we run into problems, because $a \bmod b = 0$ if $a = b$, and $b \bmod a = 0$ if $b = a$, so then $a \bmod b = b \bmod a$, disproving the theorem. Here's the disproof:

Disproof: The theorem is false: if $a = b = 2$, for instance, then $2 \bmod 2 = 2 \bmod 2$.

In the process of finding this counterexample, though, we found out something more than was asked for: we know exactly those conditions that make $a \bmod b = b \bmod a$. Thus we are able to prove a modified version of the theorem.

Theorem 8   $a \bmod b = b \bmod a$ iff $a = b$.

Since this is an if and only if proof, we have to do it in two directions. As is often the case in if and only if proofs, one direction is much easier to do than the other. We will do the easy direction first.

Proof:

$\rightarrow$

We assume $a = b$ and prove $a \bmod b = b \bmod a$. But this is clearly true, since $x \bmod x = 0$ for all $x$, and $a$ and $b$ are equal.

$\leftarrow$

Here we have to prove that if $a \bmod b = b \bmod a$, then $a$ = $b$. Try to find a direct proof, and then give up and do the contrapositive: assume $a \not= b$, and prove that $a \bmod b \not= b \bmod a$. There are two possible cases: $a < b$, and $a > b$ (we've already assumed $a \not= b$).

$a < b$

Then $a \bmod b = a$ . But by definition, $b \bmod a$ is strictly less than $a$, so it cannot be equal to $a$ and hence can't be equal to $a \bmod b$.

$a > b$

Then $b < a$, and the proof is the same as above with $a$ replaced by $b$ and $b$ replaced by $a$.