Number Theory

Review of integers and prime numbers followed by a comprehensive presentation of congruence theory. Dedication Preface 3 Congruence Concepts 4 Basic Congruence Operations 5 Linear Congruences 6 Order, Primitive Roots, and Indices of Integers 7 Quadratic and Higher Order Congruences Appendix A The Greek Alphabet A ppendix B Verification Procedures Chapter 1 Example 1-1 1.1 Algebraic Properties of Integers 1.2 Even and Odd Integers Example 1.2-1 Example 1.2-2 Proposition 1.2-1: Example 1.2-3 Example 1.2-4 Proposition 1.2-2: 1.3 Definition of Prime numbers Example 1.3-1 Example 1.3-2 1.4 Prime Factorization of Integers Example 1.4-1 Proposition 1.4-1: Proposition 1.4-2: Proposition 1.4-3: Proposition 1.4-5: Example 1.4-2 1.5 Determining Prime Numbers 1.5.1 Trial Division 1.5.2 The Sieve of Eratosthenes Example 1.5-1 1.6 Unique Factorization Theorem Proposition 1.6-1 (Unique factorization theorem): Example 1.6-1 1.7 Mersenne Primes Proposition 1.7-1: 1.8 Infinite Number of Prime Numbers Proposition 1.8-1 (Euclid’s theorem on the infinitude of prime numbers): Example 1.8-1 1.9 The Euler Product Formula 1.10 The Riemann Zeta Function 1.10.1 Definition of the Riemann Zeta and Xi Functions 1.10.2 Zeros of the Riemann Zeta Function 1.10.3 The Riemann Hypothesis 1.11 The Number of Primes Chapter 2 2.1 Divisors Example 2.1-1 Example 2.1-2 Example 2.1-3 Example 2.1-4 Example 2.1-5 Example 2.1-6 Proposition 2.1-1: Proposition 2.1-2: Proposition 2.1-3: 2.1.1 The Division Algorithm Proposition 2.1-4 (Division algorithm): Example 2.1-7 Example 2.1-8 Example 2.1-9 2.1.2 Common Divisor Example 2.1-10 2.1.3 Greatest Common Divisor Proposition 2.1-5: Example 2.1-11 Proposition 2.1-6: Example 2.1-12 Example 2.1-13 d | (2 i a) d | (2 i b) Proposition 2.1-7: Proposition 2.1-8: Example 2.1-14 Example 2.1-15 Proposition 2.1-10: Proposition 2.1-11 (Bezout’s identity): Example 2.1-16 Proposition 2.1-12: Proposition 2.1-13: Proposition 2.1-14: Proposition 2.1-15: Example 2.1-17 Proposition 2.1-16: Proposition 2.1-17: Proposition 2.1-18: Proposition 2.1-19: Proposition 2.1-20: Proposition 2.1-21: Proposition 2.1-22: Proposition 2.1-23: Example 2.1-18 Proposition 2.1-24: Proposition 2.1-25: Example 2.1-19 Example 2.2-1 2.2 Greatest Integer Function Example 2.2-2 2.3 Relatively Prime Example 2.3-1 Example 2.3-2 Proposition 2.3-1: Proposition 2.3-2: Proposition 2.3-3: Proposition 2.3-4: Proposition 2.3-5: Proposition 2.3-6: Proposition 2.3-7: Proposition 2.3-8: Example 2.3-4 Proposition 2.3-9: Proposition 2.3-10: Proposition 2.3-11: 2.4 Euclid's Lemma Example 2.4-1 Example 2.4-2 Proposition 2.4-2: Example 2.4-3 Proposition 2.4-3: Proposition 2.4-4: Proposition 2.4-5: n Proposition 2.4-7: Proposition 2.4-6: Proposition 2.4-8: Proposition 2.4-9: Proposition 2.4-10: Proposition 2.4-11: Proposition 2.4-12: Proposition 2.4-13: 2.5 The Euclidean Algorithm Proposition 2.5-1 (The Euclidean algorithm): Example 2.5-2 Example 2.5-3 Example 2.5-4 2.6 Multiplicative Functions Proposition 2.6-1: Proposition 2.6-2: Proposition 2.6-4: F (m in) = [ f (m) i f (n)] i [ g (m) i g (n)] 2.7 Divisors of an Integer Example 2.7-2 Proposition 2.7-2: 1)=П (a-+1) f (m i n) = f (m) i f (n) Proposition 2.7-3: 2.8 Least Common Multiple Proposition 2.8-1: Example 2.8-1 Example 2.8-2 Proposition 2.8-2: Example 2.8-3 Proposition 2.8-3: Example 2.8-4 Proposition 2.8-4: 2.9 Properties of gcd and lcm Proposition 2.9-2: Example 2.9-1 Example 2.9-2 Proposition 2.9-3: Proposition 2.9-4: 2.10 Euler’s Phi-Function Example 2.10-1 Proposition 2.10-1: Proposition 2.10-2 (Euler, 1763): Example 2.10-2 Proposition 2.10-3 (Gauss, 1801, Article 39): Example 2.10-3 Proposition 2.10-4: Example 2.10-4 2.11 Perfect Numbers Proposition 2.11-1: Proposition 2.11-2: ct(n) =TTict(c) = (2 - 1)i°(c) Chapter 3 3.1 The concept of Arithmetic Congruence Proposition 3.1-1: Proposition 3.1-2: 3.1.1 Congruence Equivalents 3.1.2 Congruence Properties Proposition 3.1-3: Example 3.1-1 Example 3.1-2 Example 3.1-3 Example 3.1-4 Example 3.1-5 Example 3.1-6 Example 3.1-7 Example 3.1-8 Example 3.1-9 Example 3.1-10 Example 3.1-11 Proposition 3.1-4 (Euclid’s lemma): Proposition 3.1-5 (Cancellation theorem): Example 3.1-12 3.2 Finite Number System Congruences Example 3.2-1 Example 3.2-2 3.3 Residue Class Proposition 3.3-1 (Gauss, 1801, Article 3): Proposition 3.3-2: Example 3.3-1 Example 3.3-2 Proposition 3.3-3: Example 3.3-3 Example 3.3-4 Example 3.3-5 Example 3.3-6 Example 3.3-7 Example 3.3-8 Example 3.3-9 10! = (1 i 2 i 3 i 4) i (5 i 6) i (7 i 8) i (9 i 10) 10! = (24) i (30) i (56) i (90) = (2) i (8) i (1) i (2) = 32 (modll) Example 3.3-10 Proposition 3.3-4: Proposition 3.3-5: Example 3.3-11 3.4 Euler’s Phi-Function Proposition 3.4-1: Example 3.4-2 Example 3.4-3 Proposition 3.4-2: •• p? i 1 ф( n) = n i П i=1 Proposition 3.4-3: Example 3.4-4 ф (n) = ф(pkic) = ф(pk)iф(c) Proposition 3.4-4: ф( p i q) = ф( p) i ф( q) Example 3.4-5 ф( p i q)=ф( p) i ф( q) = (p - 1) i (q - 1) ф( p i p) * ф( p) i ф( p) Proposition 3.4-5: Proposition 3.4-6: Proposition 3.4-7: ф( a2) = a2 i 1 i 1 Proposition 3.4-8: ф(3 i a) = ф(3) i ф(a) = 2 i ф(a) Ф 3 i ф(a) ф (3 i a) = ф (3a+1) i ф (c) = (3a+1 - 3a) i ф (c) Proposition 3.4-9: 3.5 Congruence Definition of Even AND ODD INTEGERS Proposition 3.6-1: Proposition 3.6-2: Proposition 3.6-3: Chapter 4 4.1 Congruence Operations 4.1.1 Addition and Subtraction of Congruences Proposition 4.1-1: Proposition 4.1-2: Example 4.1-1 4.1.2 Addition or Subtraction of an Integer from Congruences Proposition 4.1-3: Example 4.1-2 4.1.3 Multiplication of Congruences Proposition 4.1-4: Example 4.1-3 Example 4.1-4 4.1.4 Multiplication of Congruences by an integer Proposition 4.1-6: 4.1.5 Division of Congruences Example 4.1-5 Proposition 4.1-7: Example 4.1-7 Example 4.1-8 Proposition 4.1-9: Proposition 4.1-10: Proposition 4.1-11: Proposition 4.1-13: Proposition 4.1-14: Proposition 4.1-12: Example 4.1-9 4.1.6 Multiplicative Inverse of an Integer Modulo m Example 4.1-10 Proposition 4.1-15: a i a 1 = 1( mod m) Proposition 4.1-16: Example 4.1-11 Example 4.1-12 Example 4.1-13 Proposition 4.1-17: (a i a 1) i (b i b 1) i (a i b) 1 = a 1 i b 1 (mod m) (4.1-41) (1) i (1) i (a i b) 1 = a-1 i b-1 (mod m) (4.1-42) Proposition 4.1-18: Example 4.1-14 (2 i 6) i (3 i 4) i (5 i 9) i (7 i 8) = 14 = 1( modll) Proposition 4.1-20: Proposition 4.1-21: 4.1.7 Congruence of Integer powers Example 4.1-15 Example 4.1-16 Example 4.1-17 Example 4.1-18 Example 4.1-21 Example 4.1-22 P (11) = P (6)(mod5) Proposition 4.1-24: Example 4.1-23 P (10) = P (1)( mod3) Example 4.1-24 3130 Example 4.1-25 Proposition 4.1-28: Proposition 4.1-29: 4.2 Fermat’s Congruence Proposition 4.2-1: p i (p - 1) i (p - 2) i - i (p -r+1) Example 4.2-1 4.3 Fermat’s Little Theorem Proposition 4.3-1 (Fermat’s theorem): p i (p - 1) i (p - 2) i - i (p -r+1) Example 4.3-1 Example 4.3-2 Example 4.3-3 Example 4.3-4 Example 4.3-5 Example 4.3-6 Example 4.3-7 Example 4.3-8 Proposition 4.3-3: Example 4.3-9 Proposition 4.3-4: Proposition 4.3-5: Proposition 4.3-6: Proposition 4.3-7: Proposition 4.3-8: Proposition 4.3-9: p | (ag -1) Proposition 4.3-10: Proposition 4.3-11: Proposition 4.3-12: 4.4 Congruences Involving Reduced Residue Systems Proposition 4.4-1: Example 4.4-1 4.5 Euler’s Theorem Example 4.5-1 (3 i 1) i (3 i 3) i (3 i 5) i (3 i 9) i (3 i 11) i (3 i 13) = Example 4.5-2 Example 4.5-3 Example 4.5-4 Example 4.5-5 Proposition 4.5-2: Proposition 4.5-3: Proposition 4.5-4: Example 4.5-6 Proposition 4.5-5: Example 4.5-7 Chapter 5 5.1 Linear Congruences 5.1.1 Definition of Linear Congruences 5.1.2 Existence of Solutions to Linear Congruences Example 5.1-1 Example 5.1-2 Example 5.1-3 Example 5.1-4 Proposition 5.1-2: Example 5.1-5 Example 5.1-6 Proposition 5.1-3: Example 5.1-7 Example 5.1-8 Example 5.1-10 Proposition 5.1-4: Proposition 5.1-5: Proposition 5.1-6: Example 5.1-11 Example 5.1-12 Proposition 5.1-7: Proposition 5.1-8: Example 5.1-13 Example 5.1-14 5.1.3 Methods of Solving Linear Congruences 5.2 Systems of Linear Congruences Example 5.2-1 Example 5.2-2 Proposition 5.2-1: Example 5.2-3 Example 5.2-4 Proposition 5.2-2: Example 5.2-5 Example 5.2-6 Example 5.2-7 5.3 Linear Congruences in Two Variables Proposition 5.3-1: Proposition 5.3-2: Example 5.3-1 Example 5.3-2 Example 5.3-3 Proposition 5.3-3: Example 5.3-4 Proposition 5.3-4: Chapter 6 6.1 The Order of an Integer Proposition 6.1-1: Example 6.1-1 Example 6.1-2 Example 6.1-3 Proposition 6.1-2: Example 6.1-4 Proposition 6.1-4: Example 6.1-5 Proposition 6.1-5: Example 6.1-6 Proposition 6.1-6: Proposition 6.1-7: Example 6.1-7 Proposition 6.1-9: Example 6.1-8 Example 6.1-9 Proposition 6.1-10: Proposition 6.1-11: Example 6.1-10 Proposition 6.1-12: Example 6.1-11 Proposition 6.1-13: Proposition 6.1-14: Proposition 6.1-15: Example 6.1-12 Proposition 6.1-16: Proposition 6.1-17: Proposition 6.1-18: Proposition 6.1-19: 6.2 Primitive Roots 6.2.1 Definition of a Primitive Root 6.2.2 Existence of Primitive Roots Example 6.2-1 Example 6.2-2 Example 6.2-3 Proposition 6.2-1: ord m ( a ) = ф ( m ) Example 6.2-4 Example 6.2-5 Proposition 6.2-2: Example 6.2-6 Proposition 6.2-3: Example 6.2-7 Example 6.2-8 Example 6.2-9 Example 6.2-10 Proposition 6.2-4: Example 6.2-11 Example 6.2-12 6.2.3 Primitive Roots of Primes Proposition 6.2-5 (Lagrange’s theorem): Proposition 6.2-6: Proposition 6.2-7: Proposition 6.2-8: Proposition 6.2-9: Proposition 6.2-10: Example 6.2-14 Proposition 6.2-11: Example 6.2-15 Proposition 6.2-12: Proposition 6.2-14: Proposition 6.2-13: Proposition 6.2-15: Proposition 6.2-16: Proposition 6.2-18: Proposition 6.2-19: Example 6.2-16 Example 6.2-17 Example 6.2-18 Proposition 6.2-23: Example 6.2-19 Example 6.2-20 Proposition 6.2-26: Proposition 6.2-27: ordm (a) = ф( m) 6.3 Index Theory Proposition 6.3-1: Example 6.3-1 Example 6.3-2 Proposition 6.3-2: Proposition 6.3-3: Proposition 6.3-4: Proposition 6.3-5: Proposition 6.3-6: Example 6.3-3 Proposition 6.3-7: Example 6.3-4 Proposition 6.3-8: Example 6.3-5 Proposition 6.3-10: ^) i inda (b) = j iф(m) Proposition 6.3-11: Example 6.3-7 Example 6.3-6 Chapter 7 7.1 Quadratic Congruences with Prime Moduli Proposition 7.1-1: Example 7.1-1 x2 = 9 (modll) Proposition 7.1-2: Example 7.1-2 7.1.1 Definition of Quadratic Residues and Nonresidues Example 7.1-3 Example 7.1-4 Proposition 7.1-3: Proposition 7.1-4: Example 7.1-5 Example 7.1-6 Example 7.1-7 Example 7.1-8 Example 7.1-9 p | (x -1) i (x +1) 7.1.2 Existence of Quadratic Residues Proposition 7.1-6: Example 7.1-10 Example 7.1-11 Example 7.1-12 Example 7.1-13 Example 7.1-14 Example 7.1-15 Proposition 7.1-9: Proposition 7.1-10: Example 7.1-16 Proposition 7.1-11: 7.1.3 Finding Solutions of Quadratic Congruences Proposition 7.1-12: Example 7.1-17 Example 7.1-18 Example 7.1-19 Example 7.1-20 Proposition 7.1-16: Proposition 7.1-17: 7.2 Legendre’s Symbol Proposition 7.2-1: Proposition 7.2-2: Example 7.2-1 Example 7.2-2 Example 7.2-4 Example 7.2-5 Example 7.2-3 Example 7.2-6 Proposition 7.2-3: Proposition 7.2-4: Example 7.2-7 Example 7.2-8 Proposition 7.2-5: к P Г Example 7.2-9 Example 7.2-10 Proposition 7.2-6: Example 7.2-11 Example 7.2-12 Proposition 7.2-7: Example 7.2-13 Example 7.2-15 Example 7.2-16 Proposition 7.2-8: Proposition 7.2-9: Proposition 7.2-10: 7.3 Gauss’ Lemma (-1) n i r1 i r2 i - i rm i si i s2 i - i sn (mod P ) (—1) n i a i (2 i a) i (3 i a) • ••• i Example 7.3-3 Example 7.3-2 Proposition 7.3-2: Example 7.3-4 ■( 7 Y Example 7.3-5 Proposition 7.3-3: Proposition 7.3-4: Proposition 7.3-5: Proposition 7.3-6: Example 7.3-6 7.4 Quadratic Reciprocity = (-1) Example 7.4-1 (-1) - Proposition 7.4-2: Proposition 7.4-4: Proposition 7.4-5: Proposition 7.4-6: Example 7.4-2 Example 7.4-3 Proposition 7.4-7: Case 1: Case 2: Case 3: Case 4: Case 1: Case 2: Case 3: Case 4: 7.5 Quadratic Congruences with a Prime Power modulus Example 7.5-1 Proposition 7.5-2: Proposition 7.5-4: Case 2: Proposition 7.5-3: Case 4: Proposition 7.5-5: Proposition 7.5-6: Example 7.5-2 Example 7.5-3 x2 = a (mod pf1) x2 = a (mod pan) Proposition 7.6-1: pa1 i pa pa i (ь2 - a) (7.6-6) x2 = a (mod pa1) x2 = a (mod pan) Example 7.6-1 7.7 Jacobi’s Symbol Proposition 7.7-1: Proposition 7.7-2: Proposition 7.7-4: Proposition 7.7-3: Proposition 7.7-5: Proposition 7.7-6: Proposition 7.7-7: Proposition 7.7-8: Proposition 7.7-9: Proposition 7.7-10: Proposition 7.7-11: Proposition 7.7-13: Proposition 7.7-12: Example 7.7-2 = (-1) j\=ПП