## Elements of Number TheoryThis book is intended to complement my Elements oi Algebra, and it is similarly motivated by the problem of solving polynomial equations. However, it is independent of the algebra book, and probably easier. In Elements oi Algebra we sought solution by radicals, and this led to the concepts of fields and groups and their fusion in the celebrated theory of Galois. In the present book we seek integer solutions, and this leads to the concepts of rings and ideals which merge in the equally celebrated theory of ideals due to Kummer and Dedekind. Solving equations in integers is the central problem of number theory, so this book is truly a number theory book, with most of the results found in standard number theory courses. However, numbers are best understood through their algebraic structure, and the necessary algebraic concepts rings and ideals-have no better motivation than number theory. The first nontrivial examples of rings appear in the number theory of Euler and Gauss. The concept of ideal-today as routine in ring the ory as the concept of normal subgroup is in group theory-also emerged from number theory, and in quite heroic fashion. Faced with failure of unique prime factorization in the arithmetic of certain generalized "inte gers" , Kummer created in the 1840s a new kind of number to overcome the difficulty. He called them "ideal numbers" because he did not know exactly what they were, though he knew how they behaved. |

### What people are saying - Write a review

Number theory is probably the oldest branch of mathematics; as Stillwell points out, one of the earliest pieces of human writing that we possess is a four thousand year old clay tablet with a list of what we would now call Pythagorean triples. Number theory also occupies a strange place in modern mathematical education. High schools don't teach number theory, and I am an example of the fact that it's possible to graduate with a degree in math from a good university without ever taking a single class in the subject. Until recently I didn't realize that it was still an active field of research; I thought of it as just a collection of amusing trivia. Silly me. I've picked up some elementary facts about number theory more or less by osmosis (everyone with a well rounded technical education has at least heard of Euclid's proof of the infinitude of primes, or modulo arithmetic, or Fermat's little theorem), but I've never read a discussion of how number theory forms a coherent whole. What I found most interesting about this book was the connection between number theory and abstract algebra. I learned about ideals in my abstract algebra classes, and I thought of them as more or less the equivalent of normal subgroups for rings. Now that I've read this book I finally understand why ideals are interesting. It's a good illustration of how you can understand abstractions better after you've seen the concrete examples that the abstractions came from.

### Contents

Natural numbers and integers | 1 |

11 Natural numbers | 2 |

12 Induction | 3 |

13 Integers | 5 |

14 Division with remainder | 7 |

15 Binary notation | 8 |

16 Diophantine equations | 11 |

17 The Diophantus chord method | 14 |

72 The division property in Z2 | 119 |

73 The gcd in Zv2 | 121 |

74 Z3andZC3 | 123 |

75 Rational solutions of jc3 + y3 z3 + w3 | 126 |

76 The prime y3 in Zf3 | 129 |

77 Fermats last theorem for n 3 | 132 |

78 Discussion | 136 |

The four square theorem | 138 |

18 Gaussian integers | 17 |

19 Discussion | 20 |

The Euclidean algorithm | 22 |

22 The gcd by division with remainder | 24 |

23 Linear representation of the gcd | 26 |

24 Primes and factorization | 28 |

25 Consequences of unique prime factorization | 30 |

26 Linear Diophantine equations | 33 |

27 The vector Euclidean algorithm | 35 |

28 The map of relatively prime pairs | 38 |

29 Discussion | 40 |

Congruence arithmetic | 43 |

31 Congruence mod n | 44 |

32 Congruence classes and their arithmetic | 45 |

33 Inverses mod p | 48 |

34 Fermats little theorem | 51 |

35 Congruence theorems of Wilson and Lagrange | 53 |

36 Inverses mod k | 55 |

37 Quadratic Diophantine equations | 57 |

38 Primitive roots | 59 |

39 Existence of primitive roots | 62 |

310 Discussion | 63 |

The RSA cryptosystem | 66 |

42 Ingredients of RSA | 69 |

43 Exponentiation mod n | 70 |

44 RSA encryption and decryption | 72 |

45 Digital signatures | 73 |

46 Other computational issues | 74 |

The Pell equation | 76 |

51 Side and diagonal numbers | 77 |

52 The equation x2 2y2 l | 78 |

53 The group of solutions | 80 |

54 The general Pell equation and Zyn | 81 |

55 The pigeonhole argument | 84 |

56 Quadratic forms | 87 |

57 The map of primitive vectors | 90 |

58 Periodicity in the map of x2 ny2 | 95 |

59 Discussion | 99 |

The Gaussian integers | 101 |

61 Zi and its norm | 102 |

62 Divisibility and primes in Zi and Z | 103 |

63 Conjugates | 105 |

64 Division in Zi | 107 |

65 Fermats two square theorem | 109 |

66 Pythagorean triples | 110 |

67 Primes of the form 4n + 1 | 113 |

68 Discussion | 115 |

Quadratic integers | 117 |

71 The equation y³ x² + 2 | 118 |

81 Real matrices and C | 139 |

82 Complex matrices and H | 141 |

83 The quaternion units | 143 |

84 Zijk | 145 |

85 The Hurwitz integers | 147 |

86 Conjugates | 149 |

87 A prime divisor property | 151 |

88 Proof of the four square theorem | 152 |

89 Discussion | 154 |

Quadratic reciprocity | 158 |

91 Primes x² + y² x² + 2y² and x² + 3y² | 159 |

92 Statement of quadratic reciprocity | 161 |

93 Eulers criterion | 164 |

94 The value of | 167 |

95 The story so far | 169 |

96 The Chinese remainder theorem | 171 |

97 The full Chinese remainder theorem | 173 |

98 Proof of quadratic reciprocity | 175 |

99 Discussion | 178 |

Rings | 181 |

101 The ring axioms | 182 |

102 Rings and fields | 184 |

103 Algebraic integers | 186 |

104 Quadratic fields and their integers | 189 |

105 Norm and units of quadratic fields | 192 |

106 Discussion | 194 |

Ideals | 196 |

111 Ideals and the gcd | 197 |

112 Ideals and divisibility in Z 199 | 199 |

113 Principal ideal domains | 202 |

114 A nonprincipal ideal of Zv3 | 205 |

115 A nonprincipal ideal of Zv5 | 207 |

116 Ideals of imaginary quadratic fields as lattices | 209 |

117 Products and prime ideals | 211 |

118 Ideal prime factorization | 214 |

119 Discussion | 217 |

Prime ideals | 221 |

121 Ideals and congruence | 222 |

122 Prime and maximal ideals | 224 |

123 Prime ideals of imaginary quadratic fields | 225 |

124 Conjugate ideals | 227 |

125 Divisibility and containment | 229 |

126 Factorization of ideals | 230 |

127 Ideal classes | 231 |

128 Primes of the form x² + 5y² | 233 |

129 Discussion | 236 |

239 | |

245 | |