# 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

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

Overview on the topics discussed in class.

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