Proof may be what best distinguishes mathematics from other disciplines, even the sciences, which are logical, rigorous and to a greater or lesser degree (depending on the discipline) based on mathematics. By using rigorous, logically correct reasoning, we aim to prove mathematical theorems—that is, to demonstrate that something is true beyond all doubt.

It is impossible to give a formula or algorithm for proving any and all mathematical statements, yet certain approaches or strategies appear over and over in successful proofs, so studying proof itself is worthwhile. Of course, even if the subject is proof itself, we need to prove something, so in this chapter we begin our study of number theory, that is, the properties of the integers (often, but not always, the non-negative integers).

The idea of proof is central to all branches of mathematics; we concentrate on proofs involving the integers for two reasons. First, it is a very good subject in which to learn to write proofs. The proofs in number theory are typically very clean and clear; there is little in the way of abstraction to cloud one's understanding of the essential points of an argument. Secondly, the integers have a central position in mathematics and are used extensively in other fields such as computer science. Although the great twentieth century mathematician G. H. Hardy boasted that he did number theory because there was no chance that it could be construed as applied mathematics, it has in fact become enormously useful and important in the study of computation and particularly in cryptography. We also find number theory intrinsically interesting, one of the most beautiful subjects in modern mathematics, and all the more interesting because of its roots in antiquity. Unless otherwise specified, then, the universe of discourse is the set of integers, $\Z$.

1. Direct Proofs

2. Divisibility

3. Existence proofs

4. Induction

5. Uniqueness Arguments

6. Indirect Proof