ELEMENTARY NUMBER THEORY AND ELLIPTIC CURVES
CONTENTS 1 PRIME NUMBERS 1 2 THE RING OF INTEGERS MODULO N 17 3 PUBLIC KEY CRYPTOGRAPHY 39 4 QUADRATIC RECIPROCITY 55 5 CONTINUED FRACTIONS 73 6 ELLIPTIC CURVES 99 7 COMPUTATIONAL NUMBER THEORY 119 ANSWERS AND HINTS 163 REFERENCES 171 1 PRIME NUMBERS IN SECTION 1 1 WE DESCRIBE HOW THE INTEGERS ARE BUILT OUT OF THE PRIME NUMBERS 2 3 5 7 11 IN SECTION 1 2 WE DISCUSS THEOREMS ABOUT THE SET OF PRIMES NUMBERS STARTING WITH EUCLID S PROOF THAT THIS SET IS IN NITE THEN EXPLORE THE DISTRIBUTION OF PRIMES VIA THE PRIME NUMBER THEOREM AND THE RIEMANN HYPOTHESIS WITHOUT PROOFS 1 1 PRIME FACTORIZATION 1 1 1 PRIMES THE SET OF NATURAL NUMBERS IS N 1 2 3 4 AND THE SET OF INTEGERS IS Z 2 1 0 1 2 DE NITION 1 1 1 DIVIDES IF A B Z WE SAY THAT A DIVIDES B WRITTEN A B IF AC B FOR SOME C Z IN THIS CASE WE SAY A IS A DIVISOR OF B WE SAY THAT A DOES NOT DIVIDE B WRITTEN A B IF THERE IS NO C Z SUCH THAT AC B FOR EXAMPLE WE HAVE 2 6 AND 3 15 ALSO ALL INTEGERS DIVIDE 0 AND 0 DIVIDES ONLY 0 HOWEVER 3 DOES NOT DIVIDE 7 IN Z REMARK 1 1 2 THE NOTATION B A FOR B IS DIVISIBLE BY A IS COMMON IN RUSSIAN LITERATURE ON NUMBER THEORY 1 DE NITION 1 1 3 PRIME AND COMPOSITE AN INTEGER N 1 IS PRIME IF IT THE ONLY POSITIVE DIVISORS OF N ARE 1 AND N WE CALL N COMPOSITE IF N IS NOT PRIME THE NUMBER 1 IS NEITHER PRIME NOR COMPOSITE THE RST FEW PRIMES OF N ARE 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 AND THE RST FEW COMPOSITES ARE 4 6 8 9 10 12 14 15 16 18 20 21 22 24 25 26 27 28 30 32 33 34 REMARK 1 1 4 J H CONWAY ARGUES IN CON97 VIII THAT 1 SHOULD BE CONSIDERED A PRIME AND IN THE 1914 TABLE LEH14 LEHMER CONSIDERS 1 TO BE A PRIME IN THIS BOOK WE CONSIDER NEITHER 1 NOR 1 TO BE PRIME EVERY NATURAL NUMBER IS BUILT IN A UNIQUE WAY OUT OF PRIME NUMBERS THEOREM 1 1 5 FUNDAMENTAL THEOREM OF ARITHMETIC EVERY NAT URAL NUMBER CAN BE WRITTEN AS A PRODUCT OF PRIMES UNIQUELY UP TO ORDER NOTE THAT PRIMES ARE THE PRODUCTS WITH ONLY ONE FACTOR AND 1 IS THE EMPTY PRODUCT REMARK 1 1 6 THEOREM 1 1 5 WHICH WE WILL PROVE IN SECTION 1 1 4 IS TRICK IER TO PROVE THAN YOU MIGHT RST THINK FOR EXAMPLE UNIQUE FACTORIZATION FAILS IN THE RING Z 5 A B 5 A B Z C WHERE 6 FACTORS INTO IRREDUCIBLE ELEMENTS IN TWO DI ERENT WAYS 2 3 6 1 5 1 5 1 1 2 THE GREATEST COMMON DIVISOR WE WILL USE THE NOTION OF GREATEST COMMON DIVISOR OF TWO INTEGERS TO PROVE THAT IF P IS A PRIME AND P AB THEN P A OR P B PROVING THIS IS THE KEY STEP IN OUR PROOF OF THEOREM 1 1 5 DE NITION 1 1 7 GREATEST COMMON DIVISOR LET GCD A B MAX D Z D A AND D B UNLESS BOTH A AND B ARE 0 IN WHICH CASE GCD 0 0 0 FOR EXAMPLE GCD 1 2 1 GCD 6 27 3 AND FOR ANY A GCD 0 A GCD A 0 A IF A 0 THE GREATEST COMMON DIVISOR EXISTS BECAUSE IF D A THEN D A AND THERE ARE ONLY A POSITIVE INTEGERS A SIMILARLY THE GCD EXISTS WHEN B 0 2 ELEMENTARY NUMBER THEORY ELLIPTIC CURVES LEMMA 1 1 8 FOR ANY INTEGERS A AND B WE HAVE GCD A B GCD B A GCD A B GCD A B A GCD A B A PROOF WE ONLY PROVE THAT GCD A B GCD A B A SINCE THE OTHER CASES ARE PROVED IN A SIMILAR WAY SUPPOSE D A AND D B SO THERE EXIST INTEGERS C1 AND C2 SUCH THAT DC1 A AND DC2 B THEN B A DC2 DC1 D C2 C1 SO D B A THUS GCD A B GCD A B A SINCE THE SET OVER WHICH WE ARE TAKING THE MAX FOR GCD A B IS A SUBSET OF THE SET FOR GCD A B A THE SAME ARGUMENT WITH A REPLACED BY A AND B REPLACED BY B A SHOWS THAT GCD A B A GCD A B A GCD A B GCD A B WHICH PROVES THAT GCD A B GCD A B A LEMMA 1 1 9 SUPPOSE A B N Z THEN GCD A B GCD A B AN PROOF BY REPEATED APPLICATION OF LEMMA 1 1 8 WE HAVE GCD A B GCD A B A GCD A B 2A GCD A B 2N ASSUME FOR THE MOMENT THAT WE HAVE ALREADY PROVED THEOREM 1 1 5 A NATURAL AND NAIVE WAY TO COMPUTE GCD A B IS TO FACTOR A AND B AS A PRODUCT OF PRIMES USING THEOREM 1 1 5 THEN THE PRIME FACTORIZATION OF GCD A B CAN READ O FROM THAT OF A AND B FOR EXAMPLE IF A 2261 AND B 1275 THEN A 7 17 19 AND B 3 52 17 SO GCD A B 17 IT TURNS OUT THAT THE GREATEST COMMON DIVISOR OF TWO INTEGERS EVEN HUGE NUMBERS MILLIONS OF DIGITS IS SURPRISINGLY EASY TO COMPUTE USING ALGORITHM 1 1 12 BELOW WHICH COMPUTES GCD A B WITHOUT FACTORING A OR B TO MOTIVATE ALGORITHM 1 1 12 WE COMPUTE GCD 2261 1275 IN A DI ERENT WAY FIRST WE RECALL A HELPFUL FACT PROPOSITION 1 1 10 SUPPOSE THAT A AND B ARE INTEGERS WITH B 0 THEN THERE EXISTS UNIQUE INTEGERS Q AND R SUCH THAT 0 R B AND A BQ R PROOF FOR SIMPLICITY ASSUME THAT BOTH A AND B ARE POSITIVE WE LEAVE THE GENERAL CASE TO THE READER LET Q BE THE SET OF ALL NONNEGATIVE INTEGERS N SUCH THAT A BN IS NONNEGATIVE THEN Q IS NONEMPTY BECAUSE 0 Q AND Q IS BOUNDED BECAUSE A BN 0 FOR ALL N A B LET Q BE THE LARGEST ELEMENT OF Q THEN R A BQ B OTHERWISE Q 1 WOULD ALSO BE IN Q THUS Q AND R SATISFY THE EXISTENCE CONCLUSION TO PROVE UNIQUENESS SUPPOSE FOR THE SAKE OF CONTRADICTION THAT Q AND R A BQ ALSO SATISFY THE CONCLUSION BUT THAT Q Q THEN Q Q SINCE R A BQ 0 SO Q Q AND WE CAN WRITE Q Q M FOR SOME M 0 BUT THEN R A BQ A B Q M A BQ BM R BM B SINCE R 0 A CONTRADICTION 3 ELEMENTARY NUMBER THEORY ELLIPTIC CURVES