# Introduction to number theory, fall 2015

**Teacher:** Eero Saksman

**Scope:** 10 cr

**Type:** Intermediate studies

**Teaching: **

**Topics: **This is a first course in number theory, but it proceeds rigorously and treats some deeper aspects of the basic theory. In the first half of the course we learn basics on congruences and polynomial equations in integers, the crowning result being the Gauss theorem of quadratic reciprocity. The second half treats e.g. Gaussian integers, approximation of irrationals by rationals through the fascinating theory of continued fractions, basic Diophantine equations like Pell's equation or representation of integers as sums of 2 or 4 squares.

The topics of the course can be viewed as a useful piece of general mathematical knowledge. The course also suits well as an optional choice for advanced courses in the analysis line or those who study to become subject teachers in mathematics.

**Prerequisites: **A**l**gebra 1 + basic first courses like Analysis 1 and 2 or equivalent.

## News

**The course is over, thanks for participation!**- The exam (of Wednesday 25.11) is corrected and
**results can be found**in the usual place

## Teaching schedule

Weeks 36-38, 40-41 and 44-48, Tuesday 10-12 and Wednesday 9-12 in room C124. During some of the weeks there will be extra lecture on Monday 10-12.

## Exams

**The final exam is on Wednesday 25.11 at 9.00-12.00 in Room C124.** From exercises one can gather a considerable amount of extra points to the exam.The area contains all the lectures, however couple of longish proofs ('convergents yield best approximations' or 'number of different ways to express n as sum of two squares') are not demanded.

## Course material

There will probably appear sketchy notes in Finnish language on this webpage after each week's lectures. However, for all (and especially English speaking) participants the basic material for the course is covered by the nice book W.J. Le Veque: 'Fundamentals of number theory' (available as a cheap Dover paperback) and if one misses a lecture, one can see the topics treated each day by following the Logbook below.

## Registration

Did you forget to register? What to do?

## Exercises

### Assignments

- Exercise set 1 (7.9) Solutions
- Exercise set 2 (14.9) Solutions
- Exercise set 3 (21.9) Solutions
- Exercise set 4 (5.10) Solutions
- Exercise set 5 (12.10) Solutions
- Exercise set 6 (2.11) Solutions
- Exercise set 7 (9.11) Solutions
- Exercise set 8 (16.11) Solutions
- Exercise set 9 (23.11) Solutions

### Exercise classes

Group | Day | Time | Room | Instructor |
---|---|---|---|---|

1. | Monday | 12-14 | C124 | Jesse Jääsaari |

## Logbook

LeV below refers to the book mentioned in 'Course material'

Tuesday 1.9: Some history, prime numbers, basic rules of divisibility. Remainders (LVe: Thm 1.1). Existence and properties of the greatest common divisor (LeV: Thms 2.1 and 2.2).

Wednesday 2.9: G.c.d. of arbitrary many integers, further rules of divisibility LeV Cor 2 p.34. Uniqueness of prime factorization (LeV: Thm 1.2). Linear Diophantine equation in two variables (LeV: Thm 2.9), Euclidean algorithm (LeV pp. 32-34). Definition an first properties of congruences (LeV: Thm 3.1 and Thm 3.2).

Tuesday 8.9: Calculus with congruences, examples (LeV pp.47-49). Short recapitulation of basic notions of algebra: groups, commutative rings, integral domains, fields (LeV pp. 8-10). Congruence classes (mod m) (LeV pp.47-49).

Wednesday 9.9: Ring Z_m, when it is a field (LeV Thm 3.4). Complete residue systems and their characterizations. Fermat's little theorem. Applications. Reduced residue systems, Euler's phi-function, and its multiplicativity (LeV pp. 51-56). Principle of exclusion and inclusion.

Monday 14.9: Units of the ring Z_m, reduced residue systems, Euler's generalization of Fermat's little theorem, an identity for the phi-function (LeV: pp. 52 - 57). Application: RSA-coding system (beginning).

Tuesday 8.2 RSA-coding system (continued) (see Wikipedia). Chinese remainder theorem and its generalizations (LeV pp. 58-62).

Wednesday 9.2. Lagrange's theorem on the number of solutions of a polynomial congruence, corollaries, approach through Z_p, number of solution of the conguence with the polynomial x^d-1, Wilson's theorem (LeV pp. 63--65). Polynomial congruences with respect to non-prime moduli (beginning, LeV pp 65-66).

Monday 28.9: Polynomial congruences with respect to non-prime moduli ( LeV pp. 65-66). Order of an integer with respect to given moduli. Basic properties of order (LeV p. 79).

Tuesday 29.9: Primitive roots and their existence, formula for their number (LeV pp. 79-80). Applications to decimal expansions of rational numbers (beginning).

Monday 5.10 Length of the period of decimal expansion of mumber 1/p (continued), quadratic congruences, reduction to odd prime moduli, quadratic residues and nonresidues (LeV 97-100).

Tuesday 6.10 Legendre's symbol, Euler's criterion. Symbol (-1/p), computation rules for the Legendre symbol, number of primes in the arithmetic sequences 4n+1 and 4n-1, Gauss' lemma and Symbol (2/p) (LeV 99-102)

Wednesday 7.10 Second form of Gauss' lemma., Quadratic reciprocity theorem, applications, general second degree congruence equation (LeV 102-108).

Monday 26.10 On irrational and algebraic numbers. Dirichlet's theorem on approximation by rational numbers. On Pell's equation (LeV 198-200)

Tuesday 27.10 Existence and general formula for solutions of Pell's equation, algebraic and transcendemtal numbers, Liouville theorem on rational approximation of algebraic numbers. (LeV 200-202,220)

Wednesday 28.10 Proof of existence and examples of transcendental numbers, continued fractions of rational numbers via Euclid's algorithm, examples, definition of simple continued fractions, recursive formula for partial denominators, recursive formulas for the numerators and denominators of n:th convergents (LeV 220-221, 226-231 - excluding "best approximations").

Tuesday 3.11 (Convergence of continued fractions, exact error estimate, examples, bijective correspondence between irrational numbers and infinite continued fractions (LeV 234-237).

Wddnesday 4.11 Statement of Thm on best approximations, solution of Pell's equation using continued fractions (LeV 226, Thm 9.7, 245-247).

Thursday 5.11 Proof of the Thm on best approximations, Lagrange's theorem on periodic continued fractions (beginning) (LeV 227-231, 241).

Monday 9.11 Lagrange's theorem on periodic continued fractions, formulas for Pythagorean triples. (LeV 241-242)

Tuesday 10.11 Gaussian rationals and integers, Gaussian primes, decomposition into prime factors, reminder theorem, ideals are principal. (LeV 35-39)

Wednesday 11.11 Existence and properties of greatest common divisor, fundamental theorem of arithmetic for Gaussian integers, examples, determination of Gaussian primes.

Monday 16.11 Determination of numbers that are sums of two squares, number of different representation (beginning) (LeV 184-185)

Tuesday 17.11 Number of different representation (continuation), more general number fields, Lagranges theorem on 4 squares (beginning) (LeV 184-187).

Wednesday 18.11 Lagranges theorem on 4 squares (completion) (LeV 187-189) .

## Course feedback

Course feedback can be given at any point during the course. Click here.