# Appendix B. Proof Techniques

## B.1 The Nature of Mathematical Proof

A mathematical proof is a logically complete argument establishing the truth of a statement from accepted assumptions, definitions, and previously proved results.

In number theory, proofs often combine algebraic manipulation, divisibility arguments, congruences, induction, and structural reasoning. A proof must justify every essential step. Numerical examples may suggest a statement, but they do not establish it universally.

The distinction between observation and proof is fundamental. For instance,

$$
2^2-1=3,\quad 3^2-1=8,\quad 5^2-1=24
$$

suggests that $p^2-1$ is divisible by $24$ for primes $p>3$. A proof must explain why this always occurs.

## B.2 Direct Proof

A direct proof begins from the assumptions and proceeds logically to the conclusion.

Example: prove that the sum of two even integers is even.

Let

$$
a=2m,\quad b=2n
$$

for integers $m,n$. Then

$$
a+b=2m+2n=2(m+n).
$$

Since $m+n\in\mathbb{Z}$, the number $a+b$ is even.

Direct proofs are common when definitions naturally expand into algebraic expressions.

## B.3 Proof by Contrapositive

To prove

$$
P\implies Q,
$$

it is often easier to prove the logically equivalent statement

$$
\neg Q\implies \neg P.
$$

Example: prove that if $n^2$ is odd, then $n$ is odd.

Instead of proving this directly, prove the contrapositive:

If $n$ is even, then $n^2$ is even.

Let

$$
n=2k.
$$

Then

$$
n^2=4k^2=2(2k^2),
$$

so $n^2$ is even.

Therefore the original statement holds.

Contrapositive arguments are especially effective when negating the conclusion simplifies the algebraic structure.

## B.4 Proof by Contradiction

In contradiction arguments, one assumes the statement is false and derives an impossibility.

The contradiction may take several forms:

- violation of a known theorem,
- impossibility in arithmetic,
- incompatible parity,
- infinite descent,
- logical inconsistency.

### Example: irrationality of $\sqrt{2}$

Assume $\sqrt{2}$ is rational. Then

$$
\sqrt{2}=\frac{a}{b}
$$

with integers $a,b$ having no common factor and $b\ne0$.

Squaring gives

$$
a^2=2b^2.
$$

Hence $a^2$ is even, so $a$ is even. Write

$$
a=2k.
$$

Substituting,

$$
4k^2=2b^2,
$$

so

$$
b^2=2k^2.
$$

Thus $b$ is even.

Both $a$ and $b$ are even, contradicting the assumption that they share no common factor.

Therefore $\sqrt{2}$ is irrational.

Contradiction proofs are central in classical number theory.

## B.5 Proof by Cases

Sometimes a statement naturally separates into distinct situations.

Example: prove that

$$
n(n+1)
$$

is even for every integer $n$.

Every integer is either even or odd.

Case 1: $n$ is even. Then $n(n+1)$ is even.

Case 2: $n$ is odd. Then $n+1$ is even, so $n(n+1)$ is even.

Hence the product is always even.

The cases must collectively exhaust all possibilities.

## B.6 Mathematical Induction

Induction proves statements indexed by the natural numbers.

To establish $P(n)$ for all $n\ge1$:

1. Prove the base case.
2. Assume $P(n)$ is true.
3. Prove $P(n+1)$.

### Example

Prove that

$$
1+2+\cdots+n=\frac{n(n+1)}{2}.
$$

Base case:

$$
1=\frac{1\cdot2}{2}.
$$

Inductive step: assume

$$
1+2+\cdots+n=\frac{n(n+1)}{2}.
$$

Then

$$
1+2+\cdots+n+(n+1) =
\frac{n(n+1)}{2}+(n+1).
$$

Factor:

$$ =
(n+1)\left(\frac{n}{2}+1\right) =
\frac{(n+1)(n+2)}{2}.
$$

Thus the formula holds for $n+1$.

Therefore it holds for all $n\ge1$.

## B.7 Strong Induction

Strong induction assumes all previous cases.

Example: every integer $n\ge2$ factors into primes.

Base case: $2$ is prime.

Assume every integer between $2$ and $n$ factors into primes.

Consider $n+1$.

If $n+1$ is prime, the claim holds.

Otherwise,

$$
n+1=ab
$$

with

$$
1<a,b<n+1.
$$

By the inductive hypothesis, both $a$ and $b$ factor into primes. Therefore $n+1$ also factors into primes.

Strong induction is essential when smaller substructures arise naturally.

## B.8 Existence Proofs

An existence proof establishes that an object exists.

### Constructive existence

A constructive proof explicitly produces the object.

Example: there exists an even prime.

Indeed,

$$
2
$$

is even and prime.

### Nonconstructive existence

A nonconstructive proof shows existence without explicit construction.

Example: there exist irrational numbers $a,b$ such that $a^b$ is rational.

Consider

$$
x=\sqrt{2}^{\sqrt{2}}.
$$

If $x$ is rational, we are done.

If $x$ is irrational, let

$$
a=x,\quad b=\sqrt{2}.
$$

Then

$$
a^b =
\left(\sqrt{2}^{\sqrt{2}}\right)^{\sqrt{2}} =
\sqrt{2}^2 =
2,
$$

which is rational.

Thus such irrational numbers exist.

## B.9 Uniqueness Proofs

To prove uniqueness, one shows:

1. existence of an object,
2. no second distinct object can satisfy the same conditions.

Example: the quotient and remainder in the division algorithm are unique.

Suppose

$$
a=bq+r=bq'+r'
$$

with

$$
0\le r,r'<b.
$$

Subtract:

$$
b(q-q')=r'-r.
$$

Since both remainders lie between $0$ and $b-1$,

$$
|r'-r|<b.
$$

But the left side is divisible by $b$. The only multiple of $b$ with absolute value less than $b$ is $0$. Hence

$$
r=r',
$$

and therefore

$$
q=q'.
$$

## B.10 Counterexamples

A universal statement is disproved by a single counterexample.

Example:

“All primes are odd.”

Counterexample:

$$
2.
$$

Counterexamples are valuable because they reveal hidden assumptions or incorrect intuition.

In advanced mathematics, discovering a counterexample often leads to sharper definitions and deeper theory.

## B.11 Infinite Descent

Infinite descent is a special contradiction method introduced by Fermat.

One assumes a solution exists and constructs a strictly smaller solution of the same type. Repeating this process generates an infinite decreasing sequence of positive integers, which is impossible.

### Example idea

Suppose a minimal positive solution exists. Construct a smaller one. Contradiction.

Infinite descent was historically important in Diophantine equations and remains influential in arithmetic geometry.

## B.12 Equivalence Proofs

To prove

$$
P\Longleftrightarrow Q,
$$

one proves:

$$
P\implies Q
$$

and

$$
Q\implies P.
$$

Example:

An integer $n$ is even if and only if $n^2$ is even.

One direction:

$$
n \text{ even } \implies n^2 \text{ even}.
$$

Other direction:

$$
n^2 \text{ even } \implies n \text{ even}.
$$

Together these establish equivalence.

## B.13 Common Errors in Proofs

### Assuming the conclusion

A proof must not secretly use the statement being proved.

### Checking only examples

Finite verification does not prove an infinite statement.

### Ignoring quantifiers

Statements involving “for all” and “there exists” must be handled carefully.

### Division by zero

Algebraic manipulations must preserve validity.

For example,

$$
a^2=b^2
$$

does not imply

$$
a=b
$$

unless additional assumptions are given.

### Undefined operations

Expressions must be meaningful within the domain under consideration.

## B.14 Structure of Good Mathematical Writing

A proof should satisfy several principles:

| Principle | Description |
|---|---|
| Precision | Every claim is logically justified |
| Clarity | The main argument is visible |
| Brevity | Unnecessary steps are omitted |
| Completeness | Essential details are included |
| Flow | The argument progresses naturally |

Good proofs balance rigor with readability.

In number theory, elegant proofs are especially valued because arithmetic phenomena often conceal deep structure beneath elementary statements.

## B.15 Strategy in Number Theory Proofs

Certain methods recur frequently in number theory.

| Technique | Typical Use |
|---|---|
| Modular arithmetic | divisibility and residues |
| Induction | recursive structure |
| Contradiction | irrationality and infinitude |
| Factorization | prime decomposition |
| Infinite descent | Diophantine equations |
| Counting arguments | combinatorial number theory |
| Bounding arguments | analytic estimates |
| Symmetry | algebraic identities |

Experienced mathematicians often recognize the correct method from structural features of the problem.

## B.16 Reading and Constructing Proofs

Learning proofs requires active engagement.

When reading a proof:

1. Identify the assumptions.
2. Determine the target conclusion.
3. Locate the main idea.
4. Verify each inference.
5. Reconstruct the argument independently.

When constructing a proof:

1. Rewrite definitions explicitly.
2. Test small examples.
3. Search for structural patterns.
4. Choose an appropriate method.
5. Organize the argument before writing.

Proof writing improves through repeated practice. Number theory is especially well suited for this development because many deep ideas arise from elementary objects.