# 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.).

## Script

The script for the lecture will be written during the semester and will be updated perpetually. Click on the links to start the download:

Script (Last update: March 28)

Notes for lecture 2a Notes for lecture 2b

## Exercise sheets

Week 1: Exercise 1a Exercise 1b Solution 1a Solution 1b

Week 2: Exercise 2a Exercise 2b Solution 2a Solution 2b

Week 3: Exercise 3a Exercise 3b Solution 3a Solution 3b

Week 4: Exercise 4a Exercise 4b Solution 4a Solution 4b

Week 5: Exercise 5a Exercise 5b

Week 6: Exercise 6a Exercise 6b

## Literature

- 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)