Lecture on Elementary Number Theory

Overview and contents

Elementary number theory is one of the oldest branches of mathematics, dating back at least to the ancient Greeks. The term "elementary" refers to the fact that the problems are simple to state, and the proofs only rely on elementary tools, e.g. basic algebra but no (or very little) calculus. However, "elementary" should not be confused with "easy". It turns out that many elementary problems are very hard to solve: Some of the most difficult and long-standing problems of modern mathematics originate from elementary number theory!

In the course, we will cover the following classical topics:

  • Prime numbers: Fundamental Theorem of Arithmetic, Euclidean Algorithm, Bertrand's postulate, Prime Number Theorem
  • Number-theoretic functions: Euler's totient function, Dirichlet convolution, Moebius inversion, perfect numbers, Mersenne primes
  • Modular arithmetic: basic group theory, Chinese Remainder Theorem, Fermat's Little Theorem, Quadratic Reciprocity Law
  • Quadratic forms: Pythagorean triples, Congruent numbers, Pell's equation and continued fractions, sums of squares, reduction theory of binary quadratic forms, Gauss composition

If time permits, we may either discuss some applications to cryptography, e.g. the RSA cryposystem, or give an overview of some more advanced topics in number theory, e.g. the Birch and Swinnerton-Dyer conjecture.

There are no special prerequisites for this course. Some familiarity with the basic notions of algebra, e.g. the definition of a group or a field, might be helpful.

Structure of the classes

We will meet twice a week, Wednesdays and Fridays. Each meeting will consist of a lecture part and an exercise part, both roughly 45 minutes long, with a short break in between. In the lecture part, I will present new material (as in a usual lecture, but only half as long!). In the following exercise part, the participants can work in small groups to solve problems together. Additionally, there will by some (optional) homework problems.

Elementary number theory is a very "hands-on" subject, where it is often useful to do some numerical experiments. There will be several (optional) exercise problems which ask you to write a small program, e.g. to list all primes, generate Pythagorean triples, or to come up with some simple conjectures based on your numerical findings. We will mainly use the free computer algebra system SageMath.

Dates of the classes

The meetings take place at the following times (starting Wednesday, February 22):

Wednesdays 12-14 in HG E 1.2
Fridays 12-14 in HG D 3.2

There will be no meetings in the week after easter (07.04., 12.04., 14.04.).


Download the script (Last update: July 18. Changes are marked in red in the text).

Download slides from the first lecture

Overview on the topics discussed in class.

Exercise sheets

Exercise 1a Exercise 1b Solution 1a Solution 1b

Exercise 2a Exercise 2b Solution 2a Solution 2b

Exercise 3a Exercise 3b Solution 3a Solution 3b

Exercise 4a Exercise 4b Solution 4a Solution 4b

Exercise 5a Exercise 5b Solution 5a Solution 5b

Exercise 6a Exercise 6b Solution 6a Solution 6b

Exercise 7a Exercise 7b Solution 7a Solution 7b

Exercise 8a Exercise 8b Solution 8a Solution 8b

Exercise 9a Exercise 9b Solution 9a Solution 9b

Exercise 10a Exercise 10b Solution 10a Solution 10b

Exercise 11a Exercise 11b Solution 11a Solution 11b

Exercise 12a Exercise 12b Solution 12a Solution 12b


  • Buell - Binary quadratic forms
  • Bundschuh - Einführung in die Zahlentheorie
  • Cox - Primes of the form x^2 + n y^2
  • Jones & Jones - Elementary Number Theory
  • Mertens - Elementare Zahlentheorie
  • Tattersall - Elementary Number Theory in Nine Chapters
  • Stein - Elementary Number Theory: Primes, Congruences and Secrets (available online)