ALGEBRA

By Y. MIMAO

CONTENTS PART I NUMBERS 1 NUMBERS 3 2 INDUCTION 9 3 EUCLID S ALGORITHM 27 4 UNIQUE FACTORIZATION 53 5 CONGRUENCE 71 PART II CONGRUENCE CLASSES AND RINGS 6 CONGRUENCE CLASSES 93 7 RINGS AND FIELDS 123 8 MATRICES AND CODES 147 PART III CONGRUENCES AND GROUPS 9 FERMAT S AND EULER S THEOREMS 171 10 APPLICATIONS OF EULER S THEOREM 201 11 GROUPS 223 12 THE CHINESE REMAINDER THEOREM 253 PART IV POLYNOMIALS 13 POLYNOMIALS 285 14 UNIQUE FACTORIZATION 295 15 THE FUNDAMENTAL THEOREM OF ALGEBRA 307 16 POLYNOMIALS IN Q X 339 17 CONGRUENCES AND THE CHINESE REMAINDER THEOREM 355 18 FAST POLYNOMIAL MULTIPLICATION 373 PART V PRIMITIVE ROOTS 19 CYCLIC GROUPS AND CRYPTOGRAPHY 387 20 CARMICHAEL NUMBERS 413 21 QUADRATIC RECIPROCITY 433 22 QUADRATIC APPLICATIONS 459 PART VI FINITE FIELDS 23 CONGRUENCE CLASSES MODULO A POLYNOMIAL 479 24 HOMOMORPHISMS AND FINITE FIELDS 495 25 BCH CODES 511 PART VII FACTORING POLYNOMIALS 26 FACTORING IN Z X 531 27 IRREDUCIBLE POLYNOMIALS 557 ANSWERS AND HINTS TO THE EXERCISES 569 REFERENCES 595 PART I NUMBERS CHAPTER 1 NUMBERS MATHEMATICS GROWS THROUGH THE DEVELOPMENT AND STUDY OF NEW CONCEPTS THE HIS TORY OF NUMBERS ILLUSTRATES THIS GROWTH ANCIENT CULTURES BEGAN MATHEMATICS BY COUNTING KEEPING TALLIES IN THE ANCIENT NEAR EAST AN INCREASINGLY URBAN ECONOMY THE NEED TO KEEP RECORDS AT RST BY THE USE OF TOKENS SMALL CLAY OBJECTS TO CORRESPOND TO QUANTITIES OF GOODS SOMETIME AROUND 3100 B C ANCIENT ACCOUNTANTS BEGAN ABSTRACTING QUANTITY FROM THE OBJECTS BEING COUNTED AND WRITTEN NUMBERS WERE BORN SEE SCHMANDT BESSERAT 1993 ONCE THE NATURAL NUMBERS 1 2 3 WERE AVAILABLE MANIPULATING THEM AND SOLV ING PROBLEMS INVOLVING NUMBERS LED TO POSITIVE FRACTIONS KNOWN TO THE ANCIENT BABYLONIANS 2000 B C WHO ALSO KNEW SOME SQUARE ROOTS AND CUBE ROOTS THE CLASSICAL GREEK GEOMETERS 400 B C STUDIED POSITIVE QUANTITIES THAT COULD BE OB TAINED FROM NATURAL NUMBERS BY THE PROCESSES OF ADDITION SUBTRACTION MULTIPLICA TION DIVISION AND TAKING SQUARE ROOTS THE NUMBER 0 DID NOT COME INTO USE HOWEVER UNTIL AFTER 300 B C NEGATIVE NUMBERS RST AROSE AROUND A D 600 BUT BECAME AC CEPTABLE ONLY IN THE 1600 S DESCARTES IN 1637 CALLED THEM FALSE AND COMPLEX NUMBERS GRADUALLY WON ACCEPTANCE BETWEEN THE EARLY 1500 S AND 1800 A PRECISE UNDERSTANDING OF THE REAL NUMBERS WAS REACHED ONLY IN THE 1870 S AS THE DOMAIN OF NUMBERS BROADENED SO DID MATHEMATICS AND ITS APPLICA TIONS FOR EXAMPLE WITH ONLY THE NATURAL NUMBERS AVAILABLE CALCULUS WOULD BE UNTHINKABLE SINCE 1800 MATHEMATICS HAS DEVELOPED MANY NEW SYSTEMS OF OBJECTS THAT CAN BE MANIPULATED IN THE SAME WAY AS THESE CLASSICAL SETS OF NUMBERS JUST AS WITH CLASSICAL NUMBERS ONCE THE DOMAIN OF NUMBERS IS EXPANDED SO DO THE USES THAT CAN BE MADE OF THEM THIS BOOK IS ABOUT THESE NEW SETS OF NUMBERS AND SOME OF THEIR USES IN THIS CHAPTER WE LL SET UP SOME NOTATION FOR CLASSICAL SETS OF NUMBERS AND IN TRODUCE THE IDEA OF AN EQUIVALENCE RELATION WHICH WILL BE THE BASIS FOR CONSTRUCTING NEW SETS OF NUMBERS IN LATER CHAPTERS FIRST NOTATION