Elementary number theory Book

	Credits
	Preface
	What Is Number Theory?	1
1	Divisibility	13
1.1	The GCD and LCM	13
1.2	The Division Algorithm	18
1.3	The Euclidean Algorithm	23
1.4	Linear Combinations	27
1.5	Congruences	33
1.6	Mathematical Induction	38
2	Prime Numbers	47
2.1	Prime Factorization	47
2.2	The Fundamental Theorem of Arithmetic	52
2.3	The Importance of Unique Factorization	55
2.4	Prime Power Factorizations	60
2.5	The Set of Primes is Infinite	65
2.6	A Formula for [tau](n)	71
3	Numerical Functions	77
3.1	The Sum of the Divisors	77
3.2	Multiplicative Functions	83
3.3	Perfect Numbers	90
3.4	Mersenne and Fermat Numbers	94
3.5	The Euler Phi Function	101
3.6	The Mobius Inversion Formula	108
4	The Algebra of Congruence Classes	117
4.1	Solving Linear Congruences	117
4.2	The Clinese Remainder Theorem	125
4.3	The Theorems of Fermat and Euler	133
4.4	Primality Testing	140
4.5	Public-Key Cryptography	148
5	Congruences of Higher Degree	159
5.1	Polynomial Congruences	159
5.2	Congruences with Prime Power Moduli	165
5.3	Quadratic Residues	172
5.4	Quadratic Reciprocity	179
5.5	Flipping a Coin over the Telephone	186
6	The Number Theory of the Reals	195
6.1	Rational and Irrational Numbers	195
6.2	Finite Continued Fractions	203
6.3	Infinite Continued Fractions	211
6.4	Decimal Representation	220
6.5	Lagrange's Theorem and Primitive Roots	226
7	Diophantine Equations	235
7.1	Pythagorean Triples	235
7.2	Sums of Two Squares	242
7.3	Sums of Four Squares	247
7.4	Sums of Fourth Powers	251
7.5	Pell's Equation	256
	Bibliography	263
	Answers to Odd-Numbered Problems	267
	Index	275