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.