Skip to content
Tutorials Center
My learning

Topics

Lesson 1 of 37 ยท Getting Started

What Is Number Theory?

Meet number theory, the study of whole numbers: primes, divisibility, congruences and their uses in cryptography. Explore patterns with Python before proving them.

Number theory is the branch of mathematics that studies the whole numbers: 1, 2, 3, their negatives and zero. It asks questions a child can understand and a professional may spend a lifetime on. Which numbers are prime? How are the primes spread out? When can an equation like xยฒ + yยฒ = zยฒ be solved with whole numbers? Why does the last digit of a power follow a cycle?

The subject is old, but it is also very practical. The padlock icon in your browser, the check digit on a book's ISBN, the hash function behind a hash table and the schedule that tells you when two buses meet again all rest on number theory. This course teaches the ideas with proofs you can follow and Python code you can run, so you can test each claim yourself before you trust it.

The big questions

Almost every topic in this course answers one of four questions about integers.

  • Divisibility: when does one integer divide another, and what is the biggest number that divides two given numbers?
  • Primes: the atoms of multiplication. Every integer greater than 1 breaks into primes in exactly one way.
  • Congruences: arithmetic on a clock. Instead of the full number, you keep only the remainder after division by a fixed modulus.
  • Equations: which equations have integer solutions, and how do you find all of them?

Four questions of number theory

Divisibility Who divides whom?
Primes The building blocks.
Congruences Arithmetic with remainders.
Equations Whole-number solutions.

The chapters of this course follow these four threads.

1 / 2

Experiment first, prove later

Number theorists often begin like experimental scientists. They compute many examples, notice a pattern, and then look for a proof. Python is a good lab for this because its integers never overflow: you can compute with numbers that have hundreds of digits using plain *, // and %.

Python Spot a pattern

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 totals are 1, 4, 9, 16, 25, ... the perfect squares. That is a conjecture so far: the sum of the first n odd numbers is nยฒ. A pattern in eight cases is not a proof, but here a proof is easy. Pair the first and last odd numbers: 1 + (2n โˆ’ 1) = 2n, then 3 + (2n โˆ’ 3) = 2n, and so on. Each pair adds up to 2n and there are n/2 pairs, so the total is nยฒ.

Patterns can also fool you. The expression nยฒ + n + 41 produces a prime for n = 0, 1, 2, and keeps going for a long time. The next example checks how long.

Python A formula that looks magical

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 formula yields primes for every n from 0 through 39 and fails at n = 40, where the value is 41 ยท 41. Forty successes feel convincing, yet the claim "always prime" is false. This is why number theory demands proofs: a pattern that holds for 40 cases says nothing about case 41.

Famous open problems

Some questions are simple to state and still unanswered.

  • Goldbach's conjecture: every even number greater than 2 is the sum of two primes. It has been checked by computer for enormous ranges but never proved.
  • Twin primes: are there infinitely many pairs of primes that differ by 2, like 11 and 13?
  • Collatz problem: start with any positive integer, halve it if even, otherwise replace it by 3n + 1. Does every start reach 1?
Python Goldbach and Collatz by computer

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.

Checking cases never settles such a problem, because there are infinitely many integers. Only a proof does, and the course shows you how proofs of this kind are built in Proofs in Number Theory.

What you will learn

The course climbs in nine chapters. First you set up the tools (this chapter). Then comes divisibility, primes and the Euclidean algorithm, followed by congruences and modular arithmetic with the Chinese remainder theorem. Later chapters cover primality tests and factoring, Diophantine equations, quadratic residues, and finally the cryptography that uses all of it, ending with projects.

You need only school algebra. A little programming helps: every example is Python, and each one runs in your browser.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which objects does number theory mainly study?

    Number theory studies the whole numbers: divisibility, primes, congruences and integer equations.
  2. 2. The formula n^2 + n + 41 gives primes for n = 0 to 39. What does that show?

    At n = 40 the value is 41 * 41. Many successes do not prove a general claim.
  3. 3. Why is Python convenient for exploring number theory?

    Python integers have arbitrary precision, so you can test claims on very large numbers.
  4. 4. Which statement about Goldbach's conjecture is true?

    It is verified for huge ranges by computer but no proof is known.

Summary

  • Number theory studies integers: divisibility, primes, congruences and integer equations.
  • It powers cryptography, hashing, check digits and scheduling.
  • Computing examples suggests conjectures, but only proofs settle them.
  • n^2 + n + 41 is a warning that a long run of successes can still end in failure.
  • Python's unlimited integers make it a good laboratory.

Next: Integers and the Division Algorithm