Number Theory
Lecture Notes
Vahagn Aslanyan1
1 www.math.cmu.edu/~vahagn/
,Contents
1 Divisibility 3
1.1 Greatest common divisors . . . . . . . . . . . . . . . . . . . . 3
1.2 Linear Diophantine equations . . . . . . . . . . . . . . . . . . 4
1.3 Primes and irreducibles . . . . . . . . . . . . . . . . . . . . . . 4
1.4 The fundamental theorem of arithmetic . . . . . . . . . . . . . 5
1.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2 Multiplicative functions 7
2.1 Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 The Möbius inversion formula . . . . . . . . . . . . . . . . . . 8
2.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3 Modular arithmetic 11
3.1 Congruences . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 Wilson’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.3 Fermat’s little theorem . . . . . . . . . . . . . . . . . . . . . . 12
3.4 The Chinese Remainder Theorem . . . . . . . . . . . . . . . . 12
3.5 Euler’s totient function . . . . . . . . . . . . . . . . . . . . . . 13
3.6 Euler’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4 Primitive roots 17
4.1 The order of an element . . . . . . . . . . . . . . . . . . . . . 17
4.2 Primitive roots modulo a prime . . . . . . . . . . . . . . . . . 18
4.3 Primitive roots modulo prime powers . . . . . . . . . . . . . . 19
4.4 The structure of (Z/2k Z)× . . . . . . . . . . . . . . . . . . . . 20
4.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5 Quadratic residues 23
5.1 The Legendre symbol and Euler’s criterion . . . . . . . . . . . 23
5.2 Gauss’s lemma . . . . . . . . . . . . . . . . . . . . . . . . . . 24
iii
,iv CONTENTS
5.3 The quadratic reciprocity law . . . . . . . . . . . . . . . . . . 25
5.4 Composite moduli . . . . . . . . . . . . . . . . . . . . . . . . . 26
5.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
6 Representation of integers by some quadratic forms 29
6.1 Sums of two squares . . . . . . . . . . . . . . . . . . . . . . . 29
6.2 Sums of four squares . . . . . . . . . . . . . . . . . . . . . . . 30
6.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
7 Diophantine equations 33
7.1 The Pythagorean equation . . . . . . . . . . . . . . . . . . . . 33
7.2 A special case of Fermat’s last theorem . . . . . . . . . . . . . 34
7.3 Rational points on quadratic curves . . . . . . . . . . . . . . . 35
7.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
8 Continued fractions 39
8.1 Finite continued fractions . . . . . . . . . . . . . . . . . . . . 39
8.2 Representation of rational numbers by continued fractions . . 41
8.3 Infinite continued fractions . . . . . . . . . . . . . . . . . . . . 41
8.4 Periodic continued fractions . . . . . . . . . . . . . . . . . . . 44
8.5 Pell’s equation . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
8.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
9 Diophantine approximations 51
9.1 Dirichlet’s theorem . . . . . . . . . . . . . . . . . . . . . . . . 51
9.2 Better approximations . . . . . . . . . . . . . . . . . . . . . . 52
9.3 Transcendental numbers and Liouville’s theorem . . . . . . . . 53
9.4 Transcendence of e . . . . . . . . . . . . . . . . . . . . . . . . 55
9.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
10 Quadratic number fields 59
10.1 Units . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
10.2 Gaussian integers . . . . . . . . . . . . . . . . . . . . . . . . . 61
10.3 Fermat’s little theorem for Gaussian integers . . . . . . . . . . 63
10.4 Using Gaussian integers to solve Diophantine equations . . . . 63
10.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
11 Chebyshev’s theorem 65
11.1 Basic estimates . . . . . . . . . . . . . . . . . . . . . . . . . . 65
11.2 Proof of Chebyshev’s theorem . . . . . . . . . . . . . . . . . . 67
11.3 On the prime number theorem . . . . . . . . . . . . . . . . . . 68
11.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
, CONTENTS v
Bibliography 70
Lecture Notes
Vahagn Aslanyan1
1 www.math.cmu.edu/~vahagn/
,Contents
1 Divisibility 3
1.1 Greatest common divisors . . . . . . . . . . . . . . . . . . . . 3
1.2 Linear Diophantine equations . . . . . . . . . . . . . . . . . . 4
1.3 Primes and irreducibles . . . . . . . . . . . . . . . . . . . . . . 4
1.4 The fundamental theorem of arithmetic . . . . . . . . . . . . . 5
1.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2 Multiplicative functions 7
2.1 Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 The Möbius inversion formula . . . . . . . . . . . . . . . . . . 8
2.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3 Modular arithmetic 11
3.1 Congruences . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 Wilson’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.3 Fermat’s little theorem . . . . . . . . . . . . . . . . . . . . . . 12
3.4 The Chinese Remainder Theorem . . . . . . . . . . . . . . . . 12
3.5 Euler’s totient function . . . . . . . . . . . . . . . . . . . . . . 13
3.6 Euler’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4 Primitive roots 17
4.1 The order of an element . . . . . . . . . . . . . . . . . . . . . 17
4.2 Primitive roots modulo a prime . . . . . . . . . . . . . . . . . 18
4.3 Primitive roots modulo prime powers . . . . . . . . . . . . . . 19
4.4 The structure of (Z/2k Z)× . . . . . . . . . . . . . . . . . . . . 20
4.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5 Quadratic residues 23
5.1 The Legendre symbol and Euler’s criterion . . . . . . . . . . . 23
5.2 Gauss’s lemma . . . . . . . . . . . . . . . . . . . . . . . . . . 24
iii
,iv CONTENTS
5.3 The quadratic reciprocity law . . . . . . . . . . . . . . . . . . 25
5.4 Composite moduli . . . . . . . . . . . . . . . . . . . . . . . . . 26
5.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
6 Representation of integers by some quadratic forms 29
6.1 Sums of two squares . . . . . . . . . . . . . . . . . . . . . . . 29
6.2 Sums of four squares . . . . . . . . . . . . . . . . . . . . . . . 30
6.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
7 Diophantine equations 33
7.1 The Pythagorean equation . . . . . . . . . . . . . . . . . . . . 33
7.2 A special case of Fermat’s last theorem . . . . . . . . . . . . . 34
7.3 Rational points on quadratic curves . . . . . . . . . . . . . . . 35
7.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
8 Continued fractions 39
8.1 Finite continued fractions . . . . . . . . . . . . . . . . . . . . 39
8.2 Representation of rational numbers by continued fractions . . 41
8.3 Infinite continued fractions . . . . . . . . . . . . . . . . . . . . 41
8.4 Periodic continued fractions . . . . . . . . . . . . . . . . . . . 44
8.5 Pell’s equation . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
8.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
9 Diophantine approximations 51
9.1 Dirichlet’s theorem . . . . . . . . . . . . . . . . . . . . . . . . 51
9.2 Better approximations . . . . . . . . . . . . . . . . . . . . . . 52
9.3 Transcendental numbers and Liouville’s theorem . . . . . . . . 53
9.4 Transcendence of e . . . . . . . . . . . . . . . . . . . . . . . . 55
9.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
10 Quadratic number fields 59
10.1 Units . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
10.2 Gaussian integers . . . . . . . . . . . . . . . . . . . . . . . . . 61
10.3 Fermat’s little theorem for Gaussian integers . . . . . . . . . . 63
10.4 Using Gaussian integers to solve Diophantine equations . . . . 63
10.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
11 Chebyshev’s theorem 65
11.1 Basic estimates . . . . . . . . . . . . . . . . . . . . . . . . . . 65
11.2 Proof of Chebyshev’s theorem . . . . . . . . . . . . . . . . . . 67
11.3 On the prime number theorem . . . . . . . . . . . . . . . . . . 68
11.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
, CONTENTS v
Bibliography 70
