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:

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:
is defined to be the unique integer such that, for
some , , , and . That is, is the remainder when is divided by . Note that from
the definition it follows that
.

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 without loss of
generality, because if , we can swap and 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 . 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 . Then (from the definition above, with and ). But , from our observation above that is always less than . Hence for any values of or . By switching around and , we get a similar proof for the case .

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

**Disproof: **The theorem is false: if , for instance, then
.

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

**Proof: **

- We assume and prove
. But this is
clearly true, since for all , and and are
equal.
- Here we have to prove that if
, then =
. Try to find a direct proof, and then give up and do
the contrapositive: assume , and prove that
. There are two possible cases: , and
(we've already assumed ).
- Then . But by definition, is strictly less than , so it cannot be equal to and hence can't be equal to .
- Then , and the proof is the same as above with replaced by and replaced by .