Direct proof

A direct proof of 'if \(P\), then \(Q\)' assumes \(P\) and reasons step by step to \(Q\). It is the most common kind of proof and the one to try first. You saw short direct proofs in lesson 1. This lesson builds the technique properly: how to set a proof up, how to find the bridge between hypothesis and conclusion, and how to handle the standard ingredients of elementary proofs, namely parity, divisibility, the division algorithm, rational numbers and inequalities. Along the way you will collect a stock of small results that later proofs use without comment.

The template

Every direct proof of a universally quantified conditional has the same skeleton. Suppose the theorem is: for every \(x\) in some set, if \(P(x)\) then \(Q(x)\).

• Begin: 'Let \(x\) be an element of the set, and suppose \(P(x)\).'

• Unpack: rewrite \(P(x)\) using definitions, introducing new variables as needed ('so there is an integer \(k\) with …').

• Bridge: use algebra, earlier results and the hypotheses to reach a statement that matches the definition of \(Q(x)\).

• Conclude: 'Therefore \(Q(x)\).' Because \(x\) was arbitrary, this proves the theorem for every \(x\).

The middle step is where the thinking happens. Start your scratch work by writing what you know at the top of the page and what you want at the bottom, both in fully unpacked form. Then work forward from the top and backward from the bottom until the two meet. The final write-up presents only the forward chain.

Parity

Every integer is even or odd, and not both. We take this as known; it follows from the division algorithm below. Parity arguments are the simplest direct proofs and appear everywhere.

Theorem. If \(n\) is an odd integer, then \(n^2 - 1\) is divisible by 8.

Scratch work. We know \(n = 2k + 1\). We want \(n^2 - 1 = 8t\) for some integer \(t\). Compute \(n^2 - 1 = 4k^2 + 4k = 4k(k + 1)\). We need an extra factor of 2, and it comes from \(k(k + 1)\): one of two consecutive integers is even, so their product is even.

Proof. Let \(n\) be odd, so \(n = 2k + 1\) for some integer \(k\). Then \(n^2 - 1 = 4k^2 + 4k = 4k(k + 1)\). The integers \(k\) and \(k + 1\) are consecutive, so one of them is even, and therefore \(k(k + 1) = 2j\) for some integer \(j\). Hence \(n^2 - 1 = 4 \cdot 2j = 8j\), which is divisible by 8. \(\blacksquare\)

The proof uses a lemma, 'the product of two consecutive integers is even', which itself has a short proof by cases: if \(k\) is even then \(k = 2a\) and \(k(k + 1) = 2a(k + 1)\); if \(k\) is odd then \(k + 1 = 2b\) is even and \(k(k + 1) = 2kb\). Lesson 6 covers proof by cases in detail.

Divisibility

Recall that \(a \mid b\) means \(b = ak\) for some integer \(k\). Divisibility has a small toolkit of properties, all with one-line direct proofs. For integers \(a, b, c, x, y\):

• If \(a \mid b\) and \(b \mid c\), then \(a \mid c\) (transitivity, proved in lesson 1).

• If \(a \mid b\) and \(a \mid c\), then \(a \mid (bx + cy)\) for all integers \(x, y\).

• If \(a \mid b\) and \(b \ne 0\), then \(|a| \le |b|\).

• If \(a \mid b\) and \(b \mid a\), then \(a = \pm b\).

Proof of the second property. Suppose \(a \mid b\) and \(a \mid c\), so \(b = ak\) and \(c = am\) for some integers \(k, m\). For any integers \(x, y\), \(bx + cy = akx + amy = a(kx + my)\), and \(kx + my\) is an integer, so \(a \mid (bx + cy)\). \(\blacksquare\)

This property, that a divisor of two numbers divides every integer combination of them, is the engine behind the Euclidean algorithm and much of MATH-351 (Number Theory). For instance, if \(d \mid a\) and \(d \mid b\) then \(d \mid (a - qb)\) for any \(q\), which is why the greatest common divisor of \(a\) and \(b\) equals the greatest common divisor of \(b\) and the remainder of \(a\) on division by \(b\).

The division algorithm

Theorem (division algorithm). For every integer \(a\) and every positive integer \(b\) there are unique integers \(q\) and \(r\) with \(a = bq + r\) and \(0 \le r < b\). We call \(q\) the quotient and \(r\) the remainder.

This is the long division you learned in school, stated precisely. We will prove it in lesson 8 using the well-ordering principle; for now we use it freely. Its power in proofs is that it splits every integer into finitely many types according to its remainder. Dividing by 2 gives the even and odd integers. Dividing by 3 gives the types \(3q\), \(3q + 1\) and \(3q + 2\). Dividing by 4 gives four types, and so on. Many statements about all integers reduce to checking each type.

For example, every perfect square leaves remainder 0 or 1 on division by 4. If \(n = 2k\) then \(n^2 = 4k^2\), remainder 0. If \(n = 2k + 1\) then \(n^2 = 4(k^2 + k) + 1\), remainder 1. As a consequence, no integer of the form \(4m + 3\) is a sum of two squares, because sums of two squares leave remainder \(0 + 0\), \(0 + 1\) or \(1 + 1\), never 3. So 3, 7, 11, 15 and 19 are not sums of two squares, a fact you can confirm by trying.

Rational numbers

A real number is rational when it equals \(a/b\) for integers \(a, b\) with \(b \ne 0\). Proofs about rational numbers unpack this definition, do algebra with fractions, and repack the result.

Theorem. The sum of two rational numbers is rational.

Proof. Let \(x\) and \(y\) be rational. Then \(x = a/b\) and \(y = c/d\) for some integers \(a, b, c, d\) with \(b \ne 0\) and \(d \ne 0\). So \(x + y = \frac{ad + bc}{bd}\). Here \(ad + bc\) and \(bd\) are integers, and \(bd \ne 0\) because a product of nonzero integers is nonzero. Therefore \(x + y\) is rational. \(\blacksquare\)

The step '\(bd \ne 0\)' is easy to forget, and without it the proof is incomplete, because the definition of rational requires a nonzero denominator. Products and differences of rationals are handled the same way. Quotients are rational too, provided the divisor is not zero. The irrational numbers are different: the sum of two irrationals can be rational, as \(\sqrt{2} + (-\sqrt{2}) = 0\) shows, so there is no theorem 'irrational plus irrational is irrational'.

Inequalities

Proofs involving inequalities need the ordering properties of the real numbers: if \(a < b\) then \(a + c < b + c\); if \(a < b\) and \(c > 0\) then \(ac < bc\); if \(a < b\) and \(c < 0\) then \(ac > bc\); and squares are never negative. A frequent strategy is to move everything to one side and recognize a square.

Theorem (AM–GM for two numbers). For all real numbers \(x, y \ge 0\), \(\sqrt{xy} \le \frac{x + y}{2}\), with equality if and only if \(x = y\).

Scratch work. We want \(2\sqrt{xy} \le x + y\), that is \(0 \le x - 2\sqrt{xy} + y\). The right side is \((\sqrt{x} - \sqrt{y})^2\). So the proof should start from the fact that a square is non-negative.

Proof. Let \(x, y \ge 0\). Since squares of real numbers are non-negative, \(0 \le (\sqrt{x} - \sqrt{y})^2 = x - 2\sqrt{xy} + y\). Adding \(2\sqrt{xy}\) to both sides and dividing by 2 gives \(\sqrt{xy} \le \frac{x + y}{2}\). Equality holds exactly when \((\sqrt{x} - \sqrt{y})^2 = 0\), that is when \(\sqrt{x} = \sqrt{y}\), which for non-negative numbers means \(x = y\). \(\blacksquare\)

Observe the direction of the write-up. The scratch work went from the goal backwards to a known fact. The proof goes forwards from the known fact to the goal. A common mistake is to write the scratch work as if it were the proof: 'assume \(\sqrt{xy} \le \frac{x+y}{2}\); then …; so \(0 \le (\sqrt{x} - \sqrt{y})^2\), which is true'. Starting from what you want to prove and arriving at something true proves nothing, because false statements can also imply true ones. (From \(1 = -1\), squaring gives \(1 = 1\).) Backward reasoning is valid only if every step can be reversed, and then you should present it forwards.

Proofs that use earlier results

Mathematics accumulates. Once a result is proved you may use it, and naming it makes the proof easier to follow. Here is a proof that uses two earlier facts.

Theorem. If \(n\) is an integer and \(n\) is not divisible by 3, then \(n^2 - 1\) is divisible by 3.

Proof. By the division algorithm, \(n = 3q + r\) with \(r \in \{0, 1, 2\}\), and \(r \ne 0\) because \(3 \nmid n\). If \(r = 1\), then \(n - 1 = 3q\), so \(3 \mid (n - 1)\). If \(r = 2\), then \(n + 1 = 3(q + 1)\), so \(3 \mid (n + 1)\). In both cases 3 divides one of the factors of \(n^2 - 1 = (n - 1)(n + 1)\), so by the toolkit above, 3 divides the product. \(\blacksquare\)

A corollary: for every prime \(p > 3\), \(24 \mid p^2 - 1\). Since \(p\) is odd, the first theorem in this lesson gives \(8 \mid p^2 - 1\). Since \(p\) is not divisible by 3, the theorem just proved gives \(3 \mid p^2 - 1\). Because \(p^2 - 1 = 8j\) and \(3 \mid 8j\), and 3 does not divide 8, a result from number theory (Euclid's lemma, proved in MATH-351) gives \(3 \mid j\), so \(24 \mid p^2 - 1\). For \(p = 5\), \(p^2 - 1 = 24\); for \(p = 7\), it is 48.

Testing before proving

Before trying to prove a claim, test it. The code below checks the corollary for primes up to 1000, tests the square-remainder fact, and searches for numbers of the form \(4m + 3\) that are sums of two squares. Finding no counterexample does not prove the results, but a single counterexample would have saved you from trying to prove something false.

def is_prime(m):
    return m > 1 and all(m % d for d in range(2, int(m ** 0.5) + 1))

primes = [p for p in range(5, 1000) if is_prime(p)]
print("24 divides p^2 - 1 for all primes 5 <= p < 1000:", all((p * p - 1) % 24 == 0 for p in primes))

print("remainders of n^2 mod 4 for n in -50..50:", sorted({(n * n) % 4 for n in range(-50, 51)}))

sums = {a * a + b * b for a in range(0, 60) for b in range(0, 60)}
bad = [n for n in range(3, 2000, 4) if n in sums]
print("numbers 4m+3 below 2000 that are sums of two squares:", bad)

# n^3 - n divisible by 6, not just 3?  test before trying to prove it
print("6 divides n^3 - n for -100..100:", all((n**3 - n) % 6 == 0 for n in range(-100, 101)))

24 divides p^2 - 1 for all primes 5 <= p < 1000: True
remainders of n^2 mod 4 for n in -50..50: [0, 1]
numbers 4m+3 below 2000 that are sums of two squares: []
6 divides n^3 - n for -100..100: True

The last line suggests a stronger result than the one we proved: \(6 \mid n^3 - n\). It is true, and the proof combines two facts you already have: among three consecutive integers one is a multiple of 3 and at least one is even. Try writing it as a practice problem.