Skip to content
Tutorials Center
My learning

Topics

Lesson 4 of 37 · Getting Started

Proofs in Number Theory

Learn the four proof methods number theory relies on: direct proof, cases by remainder, contradiction and induction, each tested with Python before you trust it.

A proof is an argument that leaves no room for doubt. In number theory that matters more than anywhere else, because a claim about integers can hold for a million cases and still fail on the next, as the formula n² + n + 41 showed. This lesson introduces the four methods that cover most proofs in the course: direct proof, case analysis, contradiction and induction.

Python plays a supporting role. A quick search for a counterexample can save you from trying to prove something false, and a table of examples often shows you which proof to attempt. But the program never replaces the proof.

Direct proof

To prove "if P then Q", assume P and reason step by step until you reach Q. Most divisibility facts go this way. Claim: if a | b and b | c then a | c.

Assume a | b and b | c. Then b = a·m and c = b·n for some integers m and n. Substituting, c = a·m·n = a·(mn), and mn is an integer, so a | c.

Notice what the proof did: it turned the definition of "divides" into an equation, did algebra, and turned the equation back into the definition. You will repeat this pattern many times.

Python Test a claim before proving it

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The second claim looks plausible, but 6 | 2·3 even though 6 divides neither 2 nor 3. It is true when a is prime, which is a theorem you will prove soon (Euclid's lemma). One counterexample is enough to kill a universal claim.

Cases by remainder

When a statement is about all integers, split them by remainder. Claim: for every integer n, n³ − n is divisible by 3.

Write n³ − n = n(n − 1)(n + 1). Look at n mod 3:

  • If n = 3q then n is a multiple of 3.
  • If n = 3q + 1 then n − 1 = 3q is a multiple of 3.
  • If n = 3q + 2 then n + 1 = 3q + 3 is a multiple of 3.

In every case one factor is a multiple of 3, so the product is too. The cases cover every integer, which is what makes the proof complete: always check that your cases leave nothing out.

Python Check the cases numerically

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last line shows that n³ − n is not always divisible by 4: a computer check can reveal which generalizations stop working.

Proof by contradiction

To prove P, assume P is false and derive something impossible. The classic example in number theory: the square root of 2 is irrational.

Suppose √2 = a/b in lowest terms (a and b share no factor). Then a² = 2b², so a² is even, hence a is even (an odd number squared is odd). Write a = 2k. Then 4k² = 2b², so b² = 2k², and b is even as well. Now both a and b are even, which contradicts "lowest terms". So √2 cannot be a fraction.

The structure to remember: assume the opposite, follow valid steps, reach a contradiction, conclude the original statement.

A second example, due to Euclid: there are infinitely many primes. Suppose there were only finitely many, p₁, p₂, ..., pₖ. Form N = p₁p₂···pₖ + 1. N leaves remainder 1 when divided by each pᵢ, so no pᵢ divides it. But N > 1 has some prime factor, which is a prime not on the list. This contradicts the assumption that the list was complete.

Python Euclid's construction in action

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Here N = 30031 is not prime (59 · 509), but its prime factors, 59 and 509, are new primes not on the list. The proof does not say that N itself is prime, only that some prime factor of N lies outside any finite list.

Mathematical induction

Induction proves a statement P(n) for all n ≥ 1 in two steps: show P(1) (the base case), and show that P(n) implies P(n + 1) (the inductive step). It is the well-ordering principle in disguise, and it is ideal for formulas.

Claim: 1 + 2 + ... + n = n(n + 1)/2. Base: for n = 1 both sides are 1. Step: assume the formula holds for n. Then 1 + ... + n + (n + 1) = n(n + 1)/2 + (n + 1) = (n + 1)(n + 2)/2, which is the formula for n + 1.

A number-theory example: 7ⁿ − 1 is divisible by 6 for every n ≥ 1. Base: 7 − 1 = 6. Step: if 7ⁿ − 1 = 6m, then 7ⁿ⁺¹ − 1 = 7·7ⁿ − 1 = 7(6m + 1) − 1 = 42m + 6 = 6(7m + 1).

Python Induction by computer is only a check

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The program confirms finite ranges only; the induction argument covers all n at once. And the last claim shows induction cannot be faked: a base case plus a hopeful guess is not a proof.

flowchart LR
  B["Base case P(1)"] --> S["Step: P(n) gives P(n+1)"]
  S --> A["P(n) holds for all n"]

Induction: a first domino falls, and each falling domino knocks over the next.

Which method to choose

Start with a direct proof, and split into remainder cases if the statement is about all integers. Reach for contradiction when the claim says something does not exist or is not possible. Use induction when the statement is indexed by n and a step from n to n + 1 is natural.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. To show that a statement about all integers is false, what is enough?

    A universal claim fails as soon as a single counterexample exists, such as 6 | 2*3 with 6 dividing neither factor.
  2. 2. In the proof that n^3 - n is divisible by 3, why split into three cases?

    The three remainder cases cover every integer, so nothing is left out.
  3. 3. In Euclid's proof, what does N = p1p2...*pk + 1 show?

    N leaves remainder 1 when divided by every listed prime, yet has some prime factor, which must be a new prime.
  4. 4. What are the two parts of a proof by induction?

    You prove P(1) and then that P(n) implies P(n+1).

Summary

  • A direct proof unfolds definitions: a | b means b = a·m.
  • Splitting by remainder gives complete case analyses for statements about all integers.
  • Contradiction proves irrationality of √2 and the infinitude of primes.
  • Induction proves formulas and divisibility statements for all n through a base case and a step.
  • Code finds counterexamples and checks ranges, but a proof covers every case.

Next: Divisibility Properties