Submitted by: Submitted by najezo
Views: 82
Words: 19682
Pages: 79
Category: Science and Technology
Date Submitted: 07/29/2014 08:17 AM
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 . . . . . . . . . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . ....