BASIC ARITHMETIC
CONTENTS CHAPTER 1 INTRODUCTION 1 1 1 ROOTS OF POLYNOMIALS 2 1 2 LINES 5 1 3 QUADRATIC EQUATIONS AND CONIC SECTIONS 7 1 4 CUBIC EQUATIONS AND ELLIPTIC CURVES 11 1 5 CURVES OF HIGHER DEGREE 14 1 6 DIOPHANTINE EQUATIONS 16 1 7 HILBERT S TENTH PROBLEM 21 1 8 EXERCISES 23 PART 1 INTEGERS POLYNOMIALS LINES AND CONGRUENCES CHAPTER 2 THE INTEGERS 29 2 1 THE AXIOMS OF Z 29 2 2 CONSEQUENCES OF THE AXIOMS 31 2 3 THE PRINCIPLE OF MATHEMATICAL INDUCTION 33 2 4 THE DIVISION THEOREM 38 2 5 THE GREATEST COMMON DIVISOR 41 2 6 EUCLID S ALGORITHM TO CALCULATE A GCD 42 2 7 BEZOUT S IDENTITY 43 2 8 INTEGRAL AND RATIONAL ROOTS OF POLYNOMIALS 47 2 9 INTEGRAL AND RATIONAL POINTS IN A LINE 48 2 10 THE FUNDAMENTAL THEOREM OF ARITHMETIC 51 2 11 EXERCISES 55 CHAPTER 3 THE PRIME NUMBERS 61 3 1 THE SIEVE OF ERATOSTHENES 62 3 2 THE IN NITUDE OF THE PRIMES 63 3 3 THEOREMS ON THE DISTRIBUTION OF PRIMES 67 3 4 FAMOUS CONJECTURES ABOUT PRIME NUMBERS 72 3 5 EXERCISES 79 CHAPTER 4 CONGRUENCES 83 4 1 THE DE NITION OF CONGRUENCE 84 4 2 BASIC PROPERTIES OF CONGRUENCES 86 4 3 CANCELLATION PROPERTIES OF CONGRUENCES 89 4 4 LINEAR CONGRUENCES 90 4 5 SYSTEMS OF LINEAR CONGRUENCES 94 4 6 APPLICATIONS 102 4 7 EXERCISES 113 CHAPTER 5 GROUPS RINGS AND FIELDS 119 5 1 Z MZ 119 5 2 GROUPS 124 5 3 RINGS 130 5 4 FIELDS 138 5 5 RINGS OF POLYNOMIALS 140 5 6 EXERCISES 149 CHAPTER 6 FINITE FIELDS 155 6 1 AN EXAMPLE 155 6 2 POLYNOMIAL CONGRUENCES 156 6 3 IRREDUCIBLE POLYNOMIALS 159 6 4 FIELDS WITH PN ELEMENTS 160 6 5 FIELDS WITH P2 ELEMENTS 161 6 6 FIELDS WITH S ELEMENTS 163 6 7 EXERCISES 164 CHAPTER 7 THE THEOREMS OF WILSON FERMAT AND EULER 167 7 1 WILSON S THEOREM 167 7 2 FERMAT S LITTLE THEOREM 170 7 3 EULER S THEOREM 176 7 4 EULER S PHI FUNCTION 181 7 5 APPLICATIONS 184 7 6 EXERCISES 188 CHAPTER 8 PRIMITIVE ROOTS 193 8 1 MULTIPLICATIVE ORDER 195 8 2 PRIMITIVE ROOTS 200 8 3 UNIVERSAL EXPONENTS 203 8 4 EXISTENCE OF PRIMITIVE ROOTS MODULO P 205 8 5 PRIMITIVE ROOTS MODULO PK 210 8 6 INDICES 214 8 7 EXISTENCE OF PRIMITIVE ROOTS MODULO M 220 8 8 THE STRUCTURE OF Z PKZ 222 8 9 APPLICATIONS 224 8 10 EXERCISES 230 PART 2 QUADRATIC CONGRUENCES AND QUADRATIC EQUATIONS CHAPTER 9 AN INTRODUCTION TO QUADRATIC EQUATIONS 237 9 1 PRODUCT OF TWO LINES 238 9 2 A CLASSI CATION PARABOLAS ELLIPSES AND HYPERBOLAS 248 9 3 RATIONAL PARAMETRIZATIONS OF CONICS 255 9 4 INTEGRAL POINTS ON QUADRATIC EQUATIONS 260 9 5 EXERCISES 268 CHAPTER 10 QUADRATIC CONGRUENCES 271 10 1 THE QUADRATIC FORMULA 272 10 2 QUADRATIC RESIDUES 275 10 3 THE LEGENDRE SYMBOL 279 10 4 THE LAW OF QUADRATIC RECIPROCITY 284 10 5 THE JACOBI SYMBOL 290 10 6 CIPOLLA S ALGORITHM 296 10 7 APPLICATIONS 298 10 8 EXERCISES 305 CHAPTER 11 THE HASSE MINKOWSKI THEOREM 309 11 1 QUADRATIC FORMS 309 11 2 THE HASSE MINKOWSKI THEOREM 313 11 3 AN EXAMPLE OF HASSE MINKOWSKI 318 11 4 POLYNOMIAL CONGRUENCES FOR PRIME POWERS 324 11 5 THE P ADIC NUMBERS 328 11 6 HENSEL S LEMMA 331 11 7 EXERCISES 333 CHAPTER 12 CIRCLES ELLIPSES AND THE SUM OF TWO SQUARES PROBLEM 337 12 1 RATIONAL AND INTEGRAL POINTS ON A CIRCLE 337 12 2 PYTHAGOREAN TRIPLES 343 12 3 FERMAT S LAST THEOREM FOR N 4 347 12 4 ELLIPSES 348 12 5 QUADRATIC FIELDS AND NORMS 350 12 6 INTEGRAL POINTS ON ELLIPSES 353 12 7 PRIMES OF THE FORM X2 BY 2 353 12 8 EXERCISES 356 CHAPTER 13 CONTINUED FRACTIONS 361 13 1 FINITE CONTINUED FRACTIONS 363 13 2 IN NITE CONTINUED FRACTIONS 370 13 3 APPROXIMATIONS OF IRRATIONAL NUMBERS 386 13 4 EXERCISES 389 CHAPTER 14 HYPERBOLAS AND PELL S EQUATION 393 14 1 SQUARE HYPERBOLAS 393 14 2 PELL S EQUATION X2 BY2 1 395 14 3 GENERALIZED PELL S EQUATIONS X2 BY2 N 401 14 4 EXERCISES 409 PART 3 CUBIC EQUATIONS AND ELLIPTIC CURVES CHAPTER 15 AN INTRODUCTION TO CUBIC EQUATIONS 413 15 1 THE PROJECTIVE LINE AND PROJECTIVE SPACE 415 15 2 SINGULAR CUBIC CURVES 422 15 3 WEIERSTRASS EQUATIONS 425 15 4 EXERCISES 433 CHAPTER 16 ELLIPTIC CURVES 437 16 1 DE NITION 438 16 2 INTEGRAL POINTS 441 16 3 THE GROUP STRUCTURE ON E Q 441 16 4 THE TORSION SUBGROUP 447 16 5 ELLIPTIC CURVES OVER FINITE FIELDS 449 16 6 THE RANK AND THE FREE PART OF E Q 455 16 7 DESCENT AND THE WEAK MORDELL WEIL THEOREM 459 16 8 HOMOGENEOUS SPACES 467 16 9 APPLICATION THE ELLIPTIC CURVE DI E HELLMAN KEY EXCHANGE 471 16 10 EXERCISES 473 CHAPTER 1 INTRODUCTION AS LONG AS ALGEBRA AND GEOMETRY HAVE BEEN SEPARATED THEIR PROGRESS HAVE BEEN SLOW AND THEIR USES LIMITED BUT WHEN THESE TWO SCIENCES HAVE BEEN UNITED THEY HAVE LENT EACH MUTUAL FORCES AND HAVE MARCHED TOGETHER TOWARDS PERFECTION THE MAIN GOAL OF THIS BOOK IS TO STUDY N Z AND Q I E THE NATURAL NUMBERS THE INTEGERS AND THE RATIONAL NUMBERS N 1 2 3 Z 3 2 1 0 1 2 3 Q M N M N Z N 0 IN THE NEXT CHAPTER WE WILL BE MUCH MORE CAREFUL DE NING THESE SETS USING AXIOMS BUT FOR NOW WE APPEAL TO OUR INTUITION OF THE PROPERTIES THAT THESE NUMBERS SATISFY ONE CAN STUDY THESE SETS OF NUMBERS FROM THEIR INTRINSIC PROPERTIES AND MUCH CAN BE GAINED FROM SUCH AN ENDEAVOR BUT IN THIS BOOK WE STUDY THESE SETS FROM THE POINT OF VIEW OF THEIR INTERACTION WITH GEOMETRIC OBJECTS GRAPHS OF POLYNOMIALS LINES IN THE PLANE CONICS ELLIPTIC CURVES ETC OUR GENERIC APPROACH WILL BE AS FOLLOWS WE WILL DE NE A GEOMETRIC OBJECT G AND THEN WE WILL TRY TO ND ALL THE POINTS IN THE GEOMETRIC OBJECT WITH COORDINATES IN N Z OR Q WHICH WE WILL DENOTE BY G N G Z AND G Q RESPECTIVELY AS WE ATTEMPT TO ND THE NATURAL INTEGRAL OR RATIONAL POINTS WE WILL DEVELOP THE THEORY THAT IS USUALLY CALLED ELEMENTARY NUMBER THEORY OUR APPROACH WILL USE THE PROBLEM OF NDING ARITHMETIC POINTS ON A GEOMETRIC OBJECT AS THE MOTIVATION FOR THE DE NITIONS AND TECHNIQUES OF ELEMENTARY NUMBER THEORY LET US BEGIN WITH OUR RST EXAMPLE 1