Number Analysis

Theory of Numbers

Divisibility Theory in the Integers, The Theory of Congruences, Number-Theoretic Functions, Primitive Roots, Quadratic Residues

Y M

Informal style based on the course 2301331 Theory of Numbers, offered at Department of Mathematics and Computer Science, Faculty of Science, Chulalongkorn University

First version April 2012 Any comment or suggestion, please write to yotsanan.m@chula.ac.th

Contents

1 Divisibility Theory in the Integers 1.1 The Division Algorithm and GCD . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 The Fundamental Theorem of Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . 1.3 The Euclidean Algorithm and Linear Diophantine Equations . . . . . . . . . . . . . 2 The Theory of Congruences 2.1 Basic Properties of Congruence 2.2 Linear Congruences . . . . . . . 2.3 Reduced Residue Systems . . . 2.4 Polynomial Congruences . . . .

1 1 5 8 13 13 16 18 21 25 25 28 31 35 35 37 41 43

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

3 Number-Theoretic Functions 3.1 Multiplicative Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 The Mobius Inversion Formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ¨ 3.3 The Greatest Integer Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Primitive Roots 4.1 The Order of an Integer Modulo n 4.2 Integers Having Primitive Roots . 4.3 nth power residues . . . . . . . . . 4.4 Hensel’s Lemma . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . ....