PROOFS FROM THE BOOK
SIX PROOFS OF THE IN?NITY OF PRIMES CHAPTER = 641 THE ?RST FEW FERMAT NUMBERS SAY, FK AND FN (K < N), THEN M DIVIDES 2, AND HENCE M = 1 OR 2 BUT M = 2 IS IMPOSSIBLE SINCE ALL FERMAT NUMBERS ARE ODD TO PROVE THE RECURSION WE USE INDUCTION ON N FOR N = 1 WE HAVE F0 = FK FN = (FN ?2)FN = = (22N ?1)(22N + 1) = 22N+1 ?1 = FN+1 ?2 ? SIX PROOFS OF THE IN?NITY OF PRIMES ?THIRD PROOF SUPPOSE P IS ?NITE AND P IS THE LARGEST PRIME WE CONSIDER THE SO-CALLED MERSENNE NUMBER 2P ?1 AND SHOW THAT ANY PRIME FACTOR Q OF 2P ?1 IS BIGGER THAN P, WHICH WILL YIELD THE DESIRED CONCLUSION LET Q BE A PRIME DIVIDING 2P ?1, SO WE HAVE 2P ?1 (MOD Q) SINCE P IS PRIME, THIS LAGRANGE’S THEOREM IF G IS A ?NITE (MULTIPLICATIVE) GROUP AND U IS A SUBGROUP, THEN |U| DIVIDES |G| ?PROOF CONSIDER THE BINARY RELA- TION A ?B : ??BA?1 ?U IT FOLLOWS FROM THE GROUP AXIOMS THAT ?IS AN EQUIVALENCE RELATION THE EQUIVALENCE CLASS CONTAINING AN ELEMENT A IS PRECISELY THE COSET UA = {XA : X ?U} SINCE CLEARLY |UA| = |U|, WE ?ND THAT G DECOMPOSES INTO EQUIVALENCE CLASSES, ALL OF SIZE |U|, AND HENCE THAT |U| DIVIDES |G| ? IN THE SPECIAL CASE WHEN U IS A CYCLIC SUBGROUP {A, A2, , AM} WE ?ND THAT M (THE SMALLEST POSITIVE INTE- GER SUCH THAT AM = 1, CALLED THE ORDER OF A) DIVIDES THE SIZE |G| OF THE GROUP IN PARTICULAR, WE HAVE A|G| = 1 MEANS THAT THE ELEMENT 2 HAS ORDER P IN THE MULTIPLICATIVE GROUP ZQ\{0} OF THE ?ELD ZQ THIS GROUP HAS Q ?1 ELEMENTS BY LAGRANGE’S THEOREM (SEE THE BOX) WE KNOW THAT THE ORDER OF EVERY ELEMENT DIVIDES THE SIZE OF THE GROUP, THAT IS, WE HAVE P | Q ?1, AND HENCE P < Q ? NOW LET US LOOK AT A PROOF THAT USES ELEMENTARY CALCULUS ?FOURTH PROOF LET ?(X) := #{P ?X : P ?P} BE THE NUMBER OF PRIMES THAT ARE LESS THAN OR EQUAL TO THE REAL NUMBER X WE NUMBER THE PRIMES P = {P1, P2, P3, } IN INCREASING ORDER CONSIDER THE NATURAL LOGARITHM LOG X, DE?NED AS LOG X = X T DT STEPS ABOVE THE FUNCTION F(T) = T NOW WE COMPARE THE AREA BELOW THE GRAPH OF F(T) = T WITH AN UPPER STEP FUNCTION (SEE ALSO THE APPENDIX ON PAGE 12 FOR THIS METHOD ) THUS FOR N ?X < N + 1 WE HAVE LOG X ? 1 + 2 + 3 + + N ?1 + N ? PK THE INNER SUM IS A GEOMETRIC SERIES WITH RATIO P, HENCE LOG X ? P?P P?X PK PK ?1 NOW CLEARLY PK ?K + 1, AND THUS PK PK ?1 = 1 + PK ?1 ?1 + K = K + K + K = ?(X) + 1 EVERYBODY KNOWS THAT LOG X IS NOT BOUNDED, SO WE CONCLUDE THAT ?(X) IS UNBOUNDED AS WELL, AND SO THERE ARE IN?NITELY MANY PRIMES ? PROOFS FROM THE BOOK NA+I,B, WHICH PROVES THAT NA,B IS THE COMPLEMENT OF AN OPEN SET AND HENCE CLOSED “PITCHING ?AT ROCKS, IN?NITELY” SO FAR THE PRIMES HAVE NOT YET ENTERED THE PICTURE — BUT HERE THEY COME SINCE ANY NUMBER N ?= 1, ?1 HAS A PRIME DIVISOR P, AND HENCE IS CONTAINED IN N0,P, WE CONCLUDE Z \ {1, ?1} = P?P N0,P NOW IF P WERE ?NITE, THEN P?P N0,P WOULD BE A ?NITE UNION OF CLOSED SETS (BY (B)), AND HENCE CLOSED CONSEQUENTLY, {1, ?1} WOULD BE AN OPEN SET, IN VIOLATION OF (A) ? ?SIXTH PROOF OUR ?NAL PROOF GOES A CONSIDERABLE STEP FURTHER AND DEMONSTRATES NOT ONLY THAT THERE ARE IN?NITELY MANY PRIMES, BUT ALSO THAT THE SERIES P?P P DIVERGES THE ?RST PROOF OF THIS IMPORTANT RESULT WAS GIVEN BY EULER (AND IS INTERESTING IN ITS OWN RIGHT), BUT OUR PROOF, DEVISED BY ERD?OS, IS OF COMPELLING BEAUTY LET P1, P2, P3, BE THE SEQUENCE OF PRIMES IN INCREASING ORDER, AND ASSUME THAT P?P PI < N PI < N 2 (1) PROOFS FROM THE BOOK N, WHERE AN IS THE SQUARE-FREE PART EVERY AN IS THUS A PRODUCT OF DIFFERENT SMALL PRIMES, AND WE CONCLUDE THAT THERE ARE PRECISELY 2K DIFFERENT SQUARE-FREE PARTS FURTHERMORE, AS BN ??N ? ? N, WE ?ND THAT THERE ARE AT MOST ? N DIFFERENT SQUARE PARTS, AND SO NS ?2K? N SINCE (2) HOLDS FOR ANY N, IT REMAINS TO ?ND A NUMBER N WITH 2K? N ?N OR 2K+1 ? ? N, AND FOR THIS N = 22K+2 WILL DO ? APPENDIX: IN?NITELY MANY MORE PROOFS OUR COLLECTION OF PROOFS FOR THE IN?NITUDE OF PRIMES CONTAINS SEVERAL OTHER OLD AND NEW TREASURES, BUT THERE IS ONE OF VERY RECENT VINTAGE THAT IS QUITE DIFFERENT AND DESERVES SPECIAL MENTION LET US TRY TO IDENTIFY SEQUENCES S OF INTEGERS SUCH THAT THE SET OF PRIMES PS THAT DIVIDE SOME MEMBER OF S IS IN?NITE EVERY SUCH SEQUENCE WOULD THEN PROVIDE ITS OWN PROOF FOR THE IN?NITY OF PRIMES THE FERMAT NUMBERS FN STUDIED IN THE SECOND PROOF FORM SUCH A SEQUENCE, WHILE THE POWERS OF 2 DON’T MANY MORE EXAMPLES ARE PROVIDED BY A THEOREM OF ISSAI SCHUR, WHO SHOWED IN 1912 THAT FOR EVERY NONCONSTANT POLYNOMIAL P(X) WITH INTEGER COEF?CIENTS THE SET OF ALL NONZERO VALUES {P(N) ?= 0 : N ?N} IS SUCH A SEQUENCE FOR THE POLYNOMIAL P(X) = X, SCHUR’S RESULT GIVES US EUCLID’S THEOREM AS ANOTHER EXAMPLE, FOR P(X) = X2 + 1 WE GET THAT THE “SQUARES PLUS ONE” CONTAIN IN?NITELY MANY DIFFERENT PRIME FACTORS THE FOLLOWING RESULT DUE TO CHRISTIAN ELSHOLTZ IS A REAL GEM: IT GENERALIZES SCHUR’S THEOREM, THE PROOF IS JUST CLEVER COUNTING, AND IT IS IN A CERTAIN SENSE BEST POSSIBLE PROOFS FROM THE BOOK 1 P?K K , WITH ?N ?{1, 0, ?1}, ?I ?0, WHERE THE ?I = ?I(N) DEPEND ON N (FOR SN = 0 WE CAN PUT ?I = 0 FOR ALL I ) THEN 2?1+ +?K ?|SN| ?22F(N) FOR SN ?= 0, AND THUS BY TAKING THE BINARY LOGARITHM 0 ??I ??1 + + ?K ?2F(N) FOR 1 ?I ?K HENCE THERE ARE NOT MORE THAN 2F(N) + 1 DIFFERENT POSSIBLE VALUES FOR EACH ?I = ?I(N) SINCE F IS MONOTONE, THIS GIVES A ?RST ESTIMATE #{DISTINCT |SN| ?= 0 FOR N ?N} ?(2F(N) + 1)K ?2(F(N)+1)K ON THE OTHER HAND, SINCE S IS ALMOST INJECTIVE ONLY C TERMS IN THE SEQUENCE CAN BE EQUAL TO 0, AND EACH NONZERO ABSOLUTE VALUE CAN OCCUR AT MOST 2C TIMES, SO WE GET THE LOWER ESTIMATE #{DISTINCT |SN| ?= 0 FOR N ?N} ?N ?C 2C ALTOGETHER, THIS GIVES N ?C 2C ?2K(F(N)+1) TAKING AGAIN THE LOGARITHM WITH BASE 2 ON BOTH SIDES, WE OBTAIN LOG2(N ?C) ?LOG2(2C) ?K (F(N) + 1) FOR ALL N THIS, HOWEVER, IS PLAINLY FALSE FOR LARGE N, AS K AND C ARE CONSTANTS, SO LOG2(N?C) LOG2N GOES TO 1 FOR N ??, WHILE F(N) LOG2N GOES TO 0 ? PROOFS FROM THE BOOK K, WHILE PS IS ?NITE BY CONSTRUCTION REFERENCES [1] B ARTMANN: EUCLID — THE CREATION OF MATHEMATICS, SPRINGER-VERLAG, NEW YORK 1999 [2] C ELSHOLTZ: PRIME DIVISORS OF THIN SEQUENCES, AMER MATH MONTHLY (2012), 331-333 [3] P ERD ?OS: ÜBER DIE REIHE P, MATHEMATICA, ZUTPHEN B 7 (1938), 1-2 [4] L EULER: INTRODUCTIO IN ANALYSIN IN?NITORUM, TOMUS PRIMUS, LAUSANNE 1748; OPERA OMNIA, SER 1, VOL 8 [5] H FÜRSTENBERG: ON THE IN?NITUDE OF PRIMES, AMER MATH MONTHLY (1955), 353 [6] I SCHUR: ÜBER DIE EXISTENZ UNENDLICH VIELER PRIMZAHLEN IN EINIGEN SPEZIELLEN ARITHMETISCHEN PROGRESSIONEN, SITZUNGSBERICHTE DER BERLINER MATH GESELLSCHAFT 11 (1912), 40-50 PROOFS FROM THE BOOK BERTRAND’S POSTULATE CHAPTER WE HAVE SEEN THAT THE SEQUENCE OF PRIME NUMBERS 2, 3, 5, 7, IS IN?NITE TO SEE THAT THE SIZE OF ITS GAPS IS NOT BOUNDED, LET N := 2 3 5 P DENOTE THE PRODUCT OF ALL PRIME NUMBERS THAT ARE SMALLER THAN K + 2, AND NOTE THAT NONE OF THE K NUMBERS N + 2, N + 3, N + 4, , N + K, N + (K + 1) IS PRIME, SINCE FOR 2 ?I ?K + 1 WE KNOW THAT I HAS A PRIME FACTOR THAT IS SMALLER THAN K + 2, AND THIS FACTOR ALSO DIVIDES N, AND HENCE ALSO N + I WITH THIS RECIPE, WE ?ND, FOR EXAMPLE, FOR K = 10 THAT NONE OF THE TEN NUMBERS 2312, 2313, 2314, , IS PRIME BUT THERE ARE ALSO UPPER BOUNDS FOR THE GAPS IN THE SEQUENCE OF PRIME NUM- BERS A FAMOUS BOUND STATES THAT “THE GAP TO THE NEXT PRIME CANNOT BE LARGER THAN THE NUMBER WE START OUR SEARCH AT ” THIS IS KNOWN AS BERTRAND’S POS- TULATE, SINCE IT WAS CONJECTURED AND VERI?ED EMPIRICALLY FOR N < 3 000 BY JOSEPH BERTRAND IT WAS ?RST PROVED FOR ALL N BY PAFNUTY CHEBYSHEV IN 1850 A MUCH SIMPLER PROOF WAS GIVEN BY THE INDIAN GENIUS RAMANUJAN OUR BOOK PROOF IS BY PAUL ERD?OS: IT IS TAKEN FROM ERD?OS’ ?RST PUBLISHED PAPER, WHICH APPEARED IN 1932, WHEN ERD?OS WAS 19 BERTRAND’S POSTULATE FOR EVERY N ?1, THERE IS SOME PRIME NUMBER P WITH N < P ?2N ?PROOF WE WILL ESTIMATE THE SIZE OF THE BINOMIAL COEF?CIENT 2N N CARE- FULLY ENOUGH TO SEE THAT IF IT DIDN’T HAVE ANY PRIME FACTORS IN THE RANGE N < P ?2N, THEN IT WOULD BE “TOO SMALL ” OUR ARGUMENT IS IN ?VE STEPS (1) WE ?RST PROVE BERTRAND’S POSTULATE FOR N ?511 FOR THIS ONE DOES NOT NEED TO CHECK 511 CASES: IT SUF?CES (THIS IS “LANDAU’S TRICK”) TO CHECK THAT 2, 3, 5, 7, 13, 23, 43, 83, 163, 317, IS A SEQUENCE OF PRIME NUMBERS, WHERE EACH IS SMALLER THAN TWICE THE PRE- VIOUS ONE HENCE EVERY INTERVAL {Y : N < Y ?2N}, WITH N ?511, CONTAINS ONE OF THESE 11 PRIMES P ?4M 2M + P ? 2M + M = (2M+1)! M!(M+1)! IS AN INTEGER, WHERE THE PRIMES THAT WE CONSIDER ALL ARE FACTORS OF THE NUMERATOR (2M + 1)!, BUT NOT OF THE DENOMINATOR M!(M + 1)! FINALLY 2M + M ?22M HOLDS SINCE 2M + M AND 2M + M + 2M + N PK PROOFS FROM THE BOOK N PK ?MAX{R : PR ?2N} TIMES HENCE THE LARGEST POWER OF P THAT DIVIDES 2N N IS NOT LARGER THAN 2N IN PARTICULAR, PRIMES P > ? 2N APPEAR AT MOST ONCE IN 2N N FURTHERMORE — AND THIS, ACCORDING TO ERD?OS, IS THE KEY FACT FOR HIS PROOF — PRIMES P THAT SATISFY 3N < P ?N DO NOT DIVIDE 2N N AT ALL! INDEED, EXAMPLES SUCH AS = 23 52 7 17 19 = 23 33 52 17 19 = 24 32 5 17 19 23 ILLUSTRATE THAT “VERY SMALL” PRIME FACTORS P < ? 2N CAN APPEAR AS HIGHER POWERS IN 2N N , “SMALL” PRIMES WITH ? 2N < P ? 3N APPEAR AT MOST ONCE, WHILE FACTORS IN THE GAP WITH 3 N P N<P?2N P NOW, THERE ARE NO MORE THAN ? 2N PRIMES IN THE ?RST FACTOR; HENCE USING (1) FOR THE SECOND FACTOR AND LETTING P(N) DENOTE THE NUMBER OF PRIMES BETWEEN N AND 2N WE GET 4N 2N < (2N) ? 2N 3 N (2N)P (N), THAT IS, N 3 < (2N) ? 2N+1+P (N) (2) (5) TAKING THE LOGARITHM TO BASE 2, THE LAST INEQUALITY IS TURNED INTO P(N) > 2N 3 LOG2(2N) ?( ? 2N + 1) (3) IT REMAINS TO VERIFY THAT THE RIGHT-HAND SIDE OF (3) IS POSITIVE FOR N LARGE ENOUGH WE SHOW THAT THIS IS THE CASE FOR N = 29 = 512 (ACTUALLY, IT HOLDS FROM N = 468 ONWARD) BY WRITING 2N ?1 = ( ? 2N ?1)( ? 2N + 1) AND CANCELLING THE ( ? 2N + 1)-FACTOR IT SUF?CES TO SHOW ? 2N ?1 > 3 LOG2(2N) FOR N ?29 (4) FOR N = 29, (4) BECOMES 31 > 30, AND COMPARING THE DERIVATIVES (?X ?1)? = ?X AND (3 LOG2 X)? = LOG X WE SEE THAT ?X ?1 GROWS FASTER THAN 3 LOG2 X FOR X > ( LOG 2)2 ?75 AND THUS CERTAINLY FOR X ?210 = 1024 ? PROOFS FROM THE BOOK K WE DRAW THE ?GURE IN THE MARGIN AND DERIVE FROM IT K < N T DT = LOG N BY COMPARING THE AREA BELOW THE GRAPH OF F(T) = K > N T DT = LOG N PROOFS FROM THE BOOK BERTRAND’S POSTULATE BY COMPARING WITH THE AREA OF THE LARGE RECTANGLES (INCLUDING THE LIGHTLY SHADED PARTS) TAKEN TOGETHER, THIS YIELDS LOG N + N < HN < LOG N + 1 IN PARTICULAR, LIM N??HN ??, AND THE ORDER OF GROWTH OF HN IS GIVEN BY LIM N?? HN LOG N = 1 BUT MUCH BETTER ESTIMATES ARE KNOWN (SEE [2]), SUCH AS HERE O DENOTES A FUNCTION F(N) SUCH THAT F(N) ?C N6 HOLDS FOR SOME CONSTANT C HN = LOG N + ? + 2N ? 12N2 + 120N4 + O LOG K YIELDS LOG((N ?1)!) < N LOG T DT < LOG(N!), WHERE THE INTEGRAL IS EASILY COMPUTED: N LOG T DT = T LOG T ?T N 1 = N LOG N ?N + 1 THUS WE GET A LOWER ESTIMATE ON N! N! > EN LOG N?N+1 = E N E N AND AT THE SAME TIME AN UPPER ESTIMATE N! = N (N ?1)! < NEN LOG N?N+1 = EN N E N HERE A MORE CAREFUL ANALYSIS IS NEEDED TO GET THE ASYMPTOTICS OF N!, AS GIVEN BY STIRLING’S FORMULA HERE F(N) ?G(N) MEANS THAT LIM N?? F(N) G(N) = 1 N! ? ? 2?N N E N AND AGAIN THERE ARE MORE PRECISE VERSIONS AVAILABLE, SUCH AS N! = ? 2?N N E N 1 + 12N + 288N2 ? 5140N3 + O ESTIMATING BINOMIAL COEF?CIENTS JUST FROM THE DE?NITION OF THE BINOMIAL COEF?CIENTS N K AS THE NUMBER OF K-SUBSETS OF AN N-SET, WE KNOW THAT THE SEQUENCE N , N , , N N OF BINOMIAL COEF?CIENTS PROOFS FROM THE BOOK ONE EASILY ?NDS THAT FOR EVERY N THE BINOMIAL COEF?CIENTS N K FORM A SEQUENCE THAT IS SYMMETRIC AND UNIMODAL: IT INCREASES TOWARDS THE MIDDLE, SO THAT THE MIDDLE BINOMIAL COEF?CIENTS ARE THE LARGEST ONES IN THE SEQUENCE PASCAL’S TRIANGLE 1 = N < N > N N = 1 HERE ?X?RESP ?X?DENOTES THE NUMBER X ROUNDED DOWN RESP ROUNDED UP TO THE NEAREST INTEGER FROM THE ASYMPTOTIC FORMULAS FOR THE FACTORIALS MENTIONED ABOVE ONE CAN OBTAIN VERY PRECISE ESTIMATES FOR THE SIZES OF BINOMIAL COEF?CIENTS HOW- EVER, WE WILL ONLY NEED VERY WEAK AND SIMPLE ESTIMATES IN THIS BOOK, SUCH AS THE FOLLOWING: N K ?2N FOR ALL K, WHILE FOR N ?2 WE HAVE N ?N/2? ?2N N , WITH EQUALITY ONLY FOR N = 2 IN PARTICULAR, FOR N ?1, 2N N ?4N 2N THIS HOLDS SINCE N ?N/2? , A MIDDLE BINOMIAL COEF?CIENT, IS THE LARGEST ENTRY IN THE SEQUENCE N + N N , N , WHOSE SUM IS 2N, AND WHOSE AVERAGE IS THUS 2N N ON THE OTHER HAND, WE NOTE THE UPPER BOUND FOR BINOMIAL COEF?CIENTS N K = N(N ?1) (N ?K + 1) K! ?NK K! ? NK 2K?1 , WHICH IS A REASONABLY GOOD ESTIMATE FOR THE “SMALL” BINOMIAL COEF?CIENTS AT THE TAILS OF THE SEQUENCE, WHEN N IS LARGE (COMPARED TO K) REFERENCES [1] P ERD ?OS: BEWEIS EINES SATZES VON TSCHEBYSCHEF, ACTA SCI MATH (SZEGED) (1930-32), 194-198 [2] R L GRAHAM, D E KNUTH & O PATASHNIK: CONCRETE MATHEMATICS A FOUNDATION FOR COMPUTER SCIENCE, ADDISON-WESLEY, READING MA 1989 [3] G H HARDY & E M WRIGHT: AN INTRODUCTION TO THE THEORY OF NUMBERS, FIFTH EDITION, OXFORD UNIVERSITY PRESS 1979 [4] P RIBENBOIM: THE NEW BOOK OF PRIME NUMBER RECORDS, SPRINGER-VERLAG, NEW YORK 1989 PROOFS FROM THE BOOK BINOMIAL COEF?CIENTS ARE (ALMOST) NEVER POWERS CHAPTER THERE IS AN EPILOGUE TO BERTRAND’S POSTULATE WHICH LEADS TO A BEAUTIFUL RE- SULT ON BINOMIAL COEF?CIENTS IN 1892 SYLVESTER STRENGTHENED BERTRAND’S POSTULATE IN THE FOLLOWING WAY: IF N ?2K, THEN AT LEAST ONE OF THE NUMBERS N, N ?1, , N ?K + HAS A PRIME DIVISOR P GREATER THAN K NOTE THAT FOR N = 2K WE OBTAIN PRECISELY BERTRAND’S POSTULATE IN 1934, ERD?OS GAVE A SHORT AND ELEMENTARY BOOK PROOF OF SYLVESTER’S RESULT, RUNNING ALONG THE LINES OF HIS PROOF OF BERTRAND’S POSTULATE THERE IS AN EQUIVALENT WAY OF STATING SYLVESTER’S THEOREM: THE BINOMIAL COEF?CIENT N K = N(N ?1) (N ?K + 1) K! (N ?2K) ALWAYS HAS A PRIME FACTOR P > K WITH THIS OBSERVATION IN MIND, WE TURN TO ANOTHER ONE OF ERD?OS’ JEWELS: WHEN IS N K EQUAL TO A POWER M?? THE CASE K = ?= 2 LEADS TO A CLASSICAL TOPIC MULTIPLYING N BY 8 AND REARRANGING TERMS GIVES (2N ?1)2 ?2(2M)2 = 1, WHICH IS A SPECIAL CASE OF PELL’S EQUATION, X2 ?2Y2 = 1 ONE LEARNS IN NUMBER THEORY THAT THIS EQUATION HAS IN?NITELY MANY POSITIVE SOLUTIONS (XK, YK), WHICH ARE GIVEN BY XK + YK ? 2 = (3 + ? 2)K FOR K ?1 THE SMALLEST EXAMPLES ARE (X1, Y1) = (3, 2), (X2, Y2) = (17, 12), AND (X3, Y3) = (99, 70), YIELDING = 12, = 62, AND = 352 FOR K = 2 AND ?> 2 THERE ARE NO FURTHER SOLUTIONS, AND FOR K = 3 IT IS KNOWN THAT N NO SOLUTIONS EXIST, AND THIS IS WHAT ERD?OS PROVED BY AN INGENIOUS ARGUMENT THEOREM THE EQUATION N K = M?HAS NO INTEGER SOLUTIONS WITH ??2 AND 4 ?K ?N ?4 PI + 1 ? K PI + 1 PROOFS FROM THE BOOK K PI + K PI ???1, AND WE HAVE OUR DESIRED CONTRADICTION, SINCE V?IS AN ?-TH POWER WE SEE THAT OUR ANALYSIS SO FAR AGREES WITH = 1402, AS 50 = 2 49 = 1 48 = 3 > 4?M? 1M? > 2N2 PROOFS FROM THE BOOK BINOMIAL COEF?CIENTS ARE (ALMOST) NEVER POWERS NOW SINCE MI ?N1/??N1/3 WE ?NALLY OBTAIN KN2/3 ?KM1M3 > (K ?1)M1M3 > N, OR K3 > N WITH THIS CONTRADICTION, THE PROOF IS COMPLETE ? REFERENCES [1] P ERD ?OS: A THEOREM OF SYLVESTER AND SCHUR, J LONDON MATH SOC 9 (1934), 282-288 [2] P ERD ?OS: ON A DIOPHANTINE EQUATION, J LONDON MATH SOC 26 (1951), 176-178 [3] K GY ?ORY: ON THE DIOPHANTINE EQUATION N K = XL, ACTA ARITHMETICA (1997), 289-295 [4] J J SYLVESTER: ON ARITHMETICAL SERIES, MESSENGER OF MATH 21 (1892), 1-19, 87-120; COLLECTED MATHEMATICAL PAPERS VOL 4, 1912, 687-731 PROOFS FROM THE BOOK REPRESENTING NUMBERS AS SUMS OF TWO SQUARES CHAPTER 1 = 12 + 2 = 12 + 3 = 4 = 22 + 5 = 22 + 6 = 7 = 8 = 22 + (WHERE P1 = 2, P2 = 3, P3 = 5, DENOTES THE SEQUENCE OF ALL PRIMES), WE ?ND THAT NK IS CONGRUENT TO 3 (MOD 4), SO IT MUST HAVE A PRIME FACTOR OF THE FORM 4M + 3, AND THIS PRIME FACTOR IS LARGER THAN PK — CONTRADICTION OUR ?RST LEMMA CHARACTERIZES THE PRIMES FOR WHICH ?1 IS A SQUARE IN THE ?ELD ZP (WHICH IS REVIEWED IN THE BOX ON THE NEXT PAGE) IT WILL ALSO GIVE US A QUICK WAY TO DERIVE THAT THERE ARE IN?NITELY MANY PRIMES OF THE FORM 4M + 1 LEMMA 1 FOR PRIMES P = 4M + 1 THE EQUATION S2 ??1 (MOD P) HAS TWO SOLUTIONS S ?{1, 2, , P?1}, FOR P = 2 THERE IS ONE SUCH SOLUTION, WHILE FOR PRIMES OF THE FORM P = 4M + 3 THERE IS NO SOLUTION ?PROOF FOR P = 2 TAKE S = 1 FOR ODD P, WE CONSTRUCT THE EQUIVALENCE RELATION ON {1, 2, , P ?1} THAT IS GENERATED BY IDENTIFYING EVERY ELEMENT WITH ITS ADDITIVE INVERSE AND WITH ITS MULTIPLICATIVE INVERSE IN ZP THUS THE “GENERAL” EQUIVALENCE CLASSES WILL CONTAIN FOUR ELEMENTS {X, ?X, X, ?X} SINCE SUCH A 4-ELEMENT SET CONTAINS BOTH INVERSES FOR ALL ITS ELEMENTS HOW- EVER, THERE ARE SMALLER EQUIVALENCE CLASSES IF SOME OF THE FOUR NUMBERS ARE NOT DISTINCT REPRESENTING NUMBERS AS SUMS OF TWO SQUARES X ??X IS IMPOSSIBLE FOR ODD P X ?X IS EQUIVALENT TO X2 ?1 THIS HAS TWO SOLUTIONS, NAMELY X = AND X = P ?1, LEADING TO THE EQUIVALENCE CLASS {1, P ?1} OF SIZE 2 X ??X IS EQUIVALENT TO X2 ??1 THIS EQUATION MAY HAVE NO SOLUTION OR TWO DISTINCT SOLUTIONS X0, P ?X0: IN THIS CASE THE EQUIVALENCE CLASS IS {X0, P ?X0} FOR P = 11 THE PARTITION IS {1, 10}, {2, 9, 6, 5}, {3, 8, 4, 7}; FOR P = 13 IT IS {1, 12}, {2, 11, 7, 6}, {3, 10, 9, 4}, {5, 8}: THE PAIR {5, 8} YIELDS THE TWO SOLUTIONS OF S2 ??1 MOD 13 THE SET {1, 2, , P?1} HAS P?1 ELEMENTS, AND WE HAVE PARTITIONED IT INTO QUADRUPLES (EQUIVALENCE CLASSES OF SIZE 4), PLUS ONE OR TWO PAIRS (EQUIVA- LENCE CLASSES OF SIZE 2) FOR P ?1 = 4M + 2 WE ?ND THAT THERE IS ONLY THE ONE PAIR {1, P?1}, THE REST IS QUADRUPLES, AND THUS S2 ??1 (MOD P) HAS NO SOLUTION FOR P ?1 = 4M THERE HAS TO BE THE SECOND PAIR, AND THIS CONTAINS THE TWO SOLUTIONS OF S2 ??1 THAT WE WERE LOOKING FOR ? LEMMA 1 SAYS THAT EVERY ODD PRIME DIVIDING A NUMBER M 2 + 1 MUST BE OF THE FORM 4M + 1 THIS IMPLIES THAT THERE ARE IN?NITELY MANY PRIMES OF THIS FORM: OTHERWISE, LOOK AT (2 3 5 QK)2 + 1, WHERE QK IS THE LARGEST SUCH PRIME THE SAME REASONING AS ABOVE YIELDS A CONTRADICTION + PRIME ?ELDS IF P IS A PRIME, THEN THE SET ZP = {0, 1, , P ?1} WITH ADDITION AND MULTIPLICATION DE?NED “MODULO P” FORMS A ?NITE ?ELD WE WILL NEED THE FOLLOWING SIMPLE PROPERTIES: FOR X ?ZP, X ?= 0, THE ADDITIVE INVERSE (FOR WHICH WE USUALLY WRITE ?X) IS GIVEN BY P ?X ?{1, 2, , P ?1} IF P > 2, THEN X AND ?X ARE DIFFERENT ELEMENTS OF ZP EACH X ?ZP\{0} HAS A UNIQUE MULTIPLICATIVE INVERSE X ?ZP\{0}, WITH XX ?1 (MOD P) THE DE?NITION OF PRIMES IMPLIES THAT THE MAP ZP ?ZP, Z ?XZ IS INJECTIVE FOR X ?= 0 THUS ON THE ?NITE SET ZP\{0} IT MUST BE SURJECTIVE AS WELL, AND HENCE FOR EACH X THERE IS A UNIQUE X ?= WITH XX ?1 (MOD P) THE SQUARES 02, 12, 22, , H2 DE?NE DIFFERENT ELEMENTS OF ZP, FOR H = ?P 2? THIS IS SINCE X2 ?Y2, OR (X + Y)(X ?Y) ?0, IMPLIES THAT X ?Y OR THAT X ??Y THE 1 + ?P 2?ELEMENTS 02, 12, , H2 ARE CALLED THE SQUARES IN ZP AT THIS POINT, LET US NOTE “ON THE ?Y” THAT FOR ALL PRIMES THERE ARE SOLUTIONS FOR X2 + Y2 ??1 (MOD P) IN FACT, THERE ARE ?P 2?+ 1 DISTINCT SQUARES X2 IN ZP, AND THERE ARE ?P 2?+ 1 DISTINCT NUMBERS OF THE FORM ?(1 + Y2) THESE TWO SETS OF NUMBERS ARE TOO LARGE TO BE DISJOINT, SINCE ZP HAS ONLY P ELEMENTS, AND THUS THERE MUST EXIST X AND Y WITH X2 ??(1 + Y2) (MOD P) PROOFS FROM THE BOOK WITH X? ?SY? ?X?? ?SY?? (MOD P) NOW WE TAKE DIFFERENCES: WE HAVE FOR P = 13, ??P?= 3 WE CONSIDER X?, Y? ?{0, 1, 2, 3} FOR S = 5, THE SUM X??SY? (MOD 13) ASSUMES THE FOLLOWING VALUES: ?? X? Y? WITH 0 < X2 + Y2 < 2P AND X2 + Y2 ?0 (MOD P) BUT P IS THE ONLY NUMBER BETWEEN 0 AND 2P THAT IS DIVISIBLE BY P THUS X2 + Y2 = P: DONE! ? OUR SECOND PROOF FOR THE PROPOSITION — ALSO CLEARLY A BOOK PROOF — WAS DISCOVERED BY ROGER HEATH-BROWN IN 1971 AND APPEARED IN 1984 (A CONDENSED “ONE-SENTENCE VERSION” WAS GIVEN BY DON ZAGIER ) IT IS SO ELEMENTARY THAT WE DON’T EVEN NEED TO USE LEMMA 1 HEATH-BROWN’S ARGUMENT FEATURES THREE LINEAR INVOLUTIONS: A QUITE OBVIOUS ONE, A HIDDEN ONE, AND A TRIVIAL ONE THAT GIVES “THE ?NAL BLOW ” THE SECOND, UNEXPECTED, INVOLUTION CORRESPONDS TO SOME HIDDEN STRUCTURE ON THE SET OF INTEGRAL SOLUTIONS OF THE EQUATION 4XY + Z2 = P PROOFS FROM THE BOOK 4 BUT IF G IS AN INVOLUTION ON U THAT HAS EXACTLY ONE ?XED POINT, THEN THE CARDINALITY OF U IS ODD PROOFS FROM THE BOOK = 73 THAT CORRESPONDS TO (X, Y, Z) = (4, 3, 5), WITH THE L SHAPE HIGH- LIGHTED WE CONSIDER TWO WINGED SQUARES “THE SAME” IF THEY ARE CONGRUENT ONE WAY TO MAKE THIS UNIQUE, SUCH THAT THE REPRESENTATION OF THE WINGED SQUARE DEPENDS ONLY ON ITS BOUNDARY CURVE, IS TO REQUIRE THAT THE L FORMED BY THE TWO EDGES IN THE UPPER RIGHT-HAND CORNER IS AT LEAST AS HIGH AS IT IS WIDE IF THIS CONDITION IS NOT SATIS?ED, THEN A MIRROR IMAGE (RE?ECTED, E G , IN A VERTICAL AXIS), WILL REPAIR THIS SO EACH SOLUTION IN T CORRESPONDS TO A UNIQUE WINGED SQUARE OF AREA 4XY + Z2 = P, AND INDEED THIS IS REVERSABLE: FROM EACH WINGED SQUARE WE CAN READ OFF A SOLUTION AND ITS WINGED SHAPE TAKING THE UNION OF THE SQUARE AND THE FOUR RECTANGLES, WE GET FOR EACH WINGED SQUARE WHAT WE WILL CALL A UNIQUE WINGED SHAPE: THIS IS A POLY- OMINO OF AREA P WITH FOUR-FOLD ROTATION SYMMETRY, WHICH HAS TWELVE VER- TICES: EIGHT CONVEX ONES WITH INNER RIGHT ANGLE AND FOUR NON-CONVEX ONES WITH OUTER RIGHT ANGLE (WE CAN’T GET A SQUARE SHAPE, SINCE P IS A PRIME, SO IT CAN’T BE A SQUARE NUMBER ) AGAIN WE WILL CONSIDER WINGED SHAPES “THE SAME” IF THEY ARE CONGRUENT, SO WE MIGHT ASSUME THAT THE L SHAPE IN THE UPPER RIGHT-HAND CORNER IS AT LEAST AS HIGH AS IT IS WIDE PROOFS FROM THE BOOK REPRESENTING NUMBERS AS SUMS OF TWO SQUARES (3, 1, 5) T : W : (1, 3, 5) (9, 1, 1) (1, 9, 1) H (3, 3, 1) (1, 7, 3) (7, 1, 3) SPIVAK’S PROOF, FOR N = 9 AND P = 37, WHERE THE SET T OF WINGED SQUARES HAS CARDINALITY 7, WHILE THE SET W OF WINGED SHAPES HAS CARDINALITY 4 PROOFS FROM THE BOOK 2 IS REPRESENTABLE: N1N2 = (X1X2 + Y1Y2)2 + (X1Y2 ?X2Y1)2 (3) IF N IS REPRESENTABLE, N = X2 + Y2, THEN ALSO NZ2 IS REPRESENTABLE, BY NZ2 = (XZ)2 + (YZ)2 FACTS (1), (2) AND (3) TOGETHER YIELD THE “IF” PART OF THE THEOREM (4) IF P = 4M + 3 IS A PRIME THAT DIVIDES A REPRESENTABLE NUMBER N = X2 + Y2, THEN P DIVIDES BOTH X AND Y, AND THUS P2 DIVIDES N IN FACT, IF WE HAD X ??0 (MOD P), THEN WE COULD ?ND X SUCH THAT XX ?1 (MOD P), MULTIPLY THE EQUATION X2+Y2 ?0 BY X2, AND THUS WE WOULD OBTAIN THAT PROOFS FROM THE BOOK BY LEMMA 1 (5) IF N IS REPRESENTABLE, AND P = 4M + 3 DIVIDES N, THEN P2 DIVIDES N, AND N/P2 IS REPRESENTABLE THIS FOLLOWS FROM (4), AND COMPLETES THE PROOF ? TWO REMARKS CLOSE OUR DISCUSSION: IF A AND B ARE TWO NATURAL NUMBERS THAT ARE RELATIVELY PRIME, THEN THERE ARE IN?NITELY MANY PRIMES OF THE FORM AM+B (M ?N) — THIS IS A FAMOUS (AND DIF?CULT) THEOREM OF DIRICHLET MORE PRECISELY, ONE CAN SHOW THAT THE NUMBER OF PRIMES P ?X OF THE FORM P = AM + B IS DESCRIBED VERY ACCURATELY FOR LARGE X BY THE FUNCTION ?(A) X LOG X, WHERE ?(A) DENOTES THE NUMBER OF B WITH 1 ?B < A THAT ARE RELATIVELY PRIME TO A (THIS IS A SUBSTANTIAL RE?NEMENT OF THE PRIME NUMBER THEOREM, WHICH WE HAD DISCUSSED ON PAGE 12 ) THIS MEANS THAT THE PRIMES FOR ?XED A AND VARYING B APPEAR ESSENTIALLY AT THE SAME RATE NEVERTHELESS, FOR EXAMPLE FOR A = 4 ONE CAN OBSERVE A RATHER SUBTLE, BUT STILL NOTICEABLE AND PERSISTENT TENDENCY TOWARDS “MORE” PRIMES OF THE FORM 4M + 3 THE DIFFERENCE BETWEEN THE COUNTS OF PRIMES OF THE FORM 4M + 3 AND THOSE OF THE FORM 4M + 1 CHANGES SIGN IN?NITELY OFTEN NEVERTHELESS, IF YOU LOOK FOR A LARGE RANDOM X, THEN CHANCES ARE THAT THERE ARE MORE PRIMES P ?X OF THE FORM P = 4M + 3 THAN OF THE FORM P = 4M + 1 THIS EFFECT IS KNOWN AS “CHEBYSHEV’S BIAS”; SEE RIESEL [4] AND RUBINSTEIN AND SARNAK [5] REFERENCES [1] F W CLARKE, W N EVERITT, L L LITTLEJOHN & S J R VORSTER: H J S SMITH AND THE FERMAT TWO SQUARES THEOREM, AMER MATH MONTHLY 106 (1999), 652-665 [2] D R HEATH-BROWN: FERMAT’S TWO SQUARES THEOREM, INVARIANT (1984), 2-5 LATEX VERSION, WITH APPENDIX ON HISTORY, JANUARY 2008, AT EPRINTS MATHS OX AC UK/677/1/INVARIANT PDF [3] I NIVEN & H S ZUCKERMAN: AN INTRODUCTION TO THE THEORY OF NUMBERS, FIFTH EDITION, WILEY, NEW YORK 1972 [4] H RIESEL: PRIME NUMBERS AND COMPUTER METHODS FOR FACTORIZATION, SECOND EDITION, PROGRESS IN MATHEMATICS 126, BIRKHÄUSER, BOSTON MA 1994 [5] M RUBINSTEIN & P SARNAK: CHEBYSHEV’S BIAS, EXPERIMENTAL MATHEMATICS 3 (1994), 173-197 [6] A SPIVAK: WINGED SQUARES [IN RUSSIAN], LECTURE NOTES FOR THE MATHEMATI- CAL CIRCLE AT MOSCOW STATE UNIVERSITY, 15TH LECTURE 2007, MMMF MSU RU/LECT/ SPIVAK/SUMMA_SQ PDF [7] A THUE: ET PAR ANTYDNINGER TIL EN TALTHEORETISK METODE, KRA VIDENSK SELSK FORH 7 (1902), 57-75 [8] S WAGON: EDITOR’S CORNER: THE EUCLIDEAN ALGORITHM STRIKES AGAIN, AMER MATH MONTHLY 97 (1990), 125-129 [9] D ZAGIER: A ONE-SENTENCE PROOF THAT EVERY PRIME P ?1 (MOD 4) IS A SUM OF TWO SQUARES, AMER MATH MONTHLY 97 (1990), 144 PROOFS FROM THE BOOK THE LAW OF QUADRATIC RECIPROCITY CHAPTER 2 , THEN P|I2 ?J2 = (I ?J)(I + J) AS 2 ?I + J ?P ?1 WE HAVE P|I ?J, THAT IS, I ?J (MOD P) FOR P = 13, THE QUADRATIC RESIDUES ARE 12 ?1, 22 ?4, 32 ?9, 42 ?3, 52 ?12, AND 62 ?10; THE NONRESIDUES ARE 2, 5, 6, 7, 8, 11 AT THIS POINT IT IS CONVENIENT TO INTRODUCE THE SO-CALLED LEGENDRE SYMBOL LET A ??0 (MOD P), THEN A P := IF A IS A QUADRATIC NONRESIDUE THE STORY BEGINS WITH FERMAT’S “LITTLE THEOREM”: FOR A ??0 (MOD P), ALTERNATIVELY, THIS IS JUST A|G| = 1 FOR THE GROUP G = Z? P (SEE THE BOX ON LAGRANGE’S THEOREM, P 4) AP?1 ?1 (MOD P) (1) IN FACT, SINCE Z? P = ZP \ {0} IS A GROUP WITH MULTIPLICATION, THE SET {1A, 2A, 3A, , (P ?1)A} RUNS AGAIN THROUGH ALL NONZERO RESIDUES, (1A)(2A) ((P ?1)A) ?1 2 (P ?1) (MOD P), AND HENCE BY DIVIDING BY (P ?1)!, WE GET AP?1 ?1 (MOD P) 2 (MOD P) FOR EXAMPLE, FOR P = 17 AND A = 3 WE HAVE 38 = (34)2 = 812 ?(?4)2 ? ?1 (MOD 17), WHILE FOR A = 2 WE GET 28 = (24)2 ?(?1)2 ?1 (MOD 17) HENCE 2 IS A QUADRATIC RESIDUE, WHILE P ), ( P ) = ?1 IF P ? 3 (MOD 4), SOMETHING WE HAVE ALREADY SEEN IN THE PREVIOUS CHAPTER THE CASE ( P) WILL FOLLOW FROM THE LEMMA OF GAUSS BELOW: ( P) = 1 IF P ? ±1 (MOD 8), WHILE ( = 1; THUS ( Q P) = ( P Q ) WHEN P ?Q ?3 (MOD 4), WE HAVE ( P Q ) = ?( Q P) THUS FOR ODD PRIMES WE GET ( P Q ) = ( Q P) UNLESS BOTH P AND Q ARE CONGRUENT TO 3 (MOD 4) EXAMPLE: ( 17) = ( 3 ) = ( 3) = ?1, SO 3 IS A NONRESIDUE MOD 17 PROOFS FROM THE BOOK ?(?1)S (MOD P), AND THEREFORE ( A P) = (?1)S, SINCE P IS ODD ? WITH THIS WE CAN EASILY COMPUTE ( 4 ? CHECK THAT S IS EVEN PRECISELY FOR P = 8K ± 1 THE LEMMA OF GAUSS IS THE BASIS FOR MANY OF THE PUBLISHED PROOFS OF THE QUADRATIC RECIPROCITY LAW THE MOST ELEGANT MAY BE THE ONE SUGGESTED BY FERDINAND GOTTHOLD EISENSTEIN, WHO HAD LEARNED NUMBER THEORY FROM GAUSS’ FAMOUS DISQUISITIONES ARITHMETICAE AND MADE IMPORTANT CONTRIBU- TIONS TO “HIGHER RECIPROCITY THEOREMS” BEFORE HIS PREMATURE DEATH AT AGE 29 HIS PROOF IS JUST COUNTING LATTICE POINTS! PROOFS FROM THE BOOK THE LAW OF QUADRATIC RECIPROCITY LET P AND Q BE ODD PRIMES, AND CONSIDER ( Q P) SUPPOSE IQ IS A MULTIPLE OF Q THAT REDUCES TO A NEGATIVE RESIDUE RI < 0 IN THE LEMMA OF GAUSS THIS MEANS THAT THERE IS A UNIQUE INTEGER J SUCH THAT ?P 2 < IQ ?JP < 0 NOTE THAT 0 < J < Q 2 SINCE 0 < I < P 2 IN OTHER WORDS, ( Q P) = (?1)S, WHERE S IS THE NUMBER OF LATTICE POINTS (X, Y), THAT IS, PAIRS OF INTEGERS X, Y SATISFYING 0 < PY ?QX < P 2, 0 < X < P 2, 0 < Y < Q 2 (3) SIMILARLY, ( P Q ) = (?1)T WHERE T IS THE NUMBER OF LATTICE POINTS (X, Y) WITH 0 < QX ?PY < Q 2, 0 < X < P 2, 0 < Y < Q 2 (4) NOW LOOK AT THE RECTANGLE WITH SIDE LENGTHS P 2, Q 2, AND DRAW THE TWO LINES PARALLEL TO THE DIAGONAL PY = QX, Y = Q PX+ 2) OR QX ?PY = Q 2 THE ?GURE SHOWS THE SITUATION FOR P = 17, Q = 11 R S P = Q = S = T = 2 ? PROOFS FROM THE BOOK I P ?I ?F, WHERE ( I P) IS THE LEGENDRE SYMBOL FOR THE PROOF WE DERIVE TWO DIFFERENT EXPRESSIONS FOR GQ AND THEN SET THEM EQUAL FIRST EXPRESSION WE HAVE EXAMPLE: TAKE P = 3, Q = 5 THEN G = ???2 AND G5 = ?5??10 = ?2?? = ?(? ??2) = ?G, CORRESPONDING TO ( 3) = ( 2 PROOFS FROM THE BOOK THE LAW OF QUADRATIC RECIPROCITY THE MULTIPLICATIVE GROUP OF A ?NITE ?ELD IS CYCLIC LET F ?BE THE MULTIPLICATIVE GROUP OF THE ?ELD F, WITH |F ?| = N WRITING ORD(A) FOR THE ORDER OF AN ELEMENT, THAT IS, THE SMALLEST POS- ITIVE INTEGER K SUCH THAT AK = 1, WE WANT TO ?ND AN ELEMENT A ?F ? WITH ORD(A) = N IF ORD(B) = D, THEN BY LAGRANGE’S THEOREM, D DIVIDES N (SEE THE MARGIN ON PAGE 4) CLASSIFYING THE ELEMENTS AC- CORDING TO THEIR ORDER, WE HAVE N = D|N ?(D), WHERE ?(D) = #{B ?F ?: ORD(B) = D} (8) IF ORD(B) = D, THEN EVERY ELEMENT BI (I = 1, , D) SATIS?ES (BI)D = AND IS THEREFORE A ROOT OF THE POLYNOMIAL XD ?1 BUT, SINCE F IS A ?ELD, XD?1 HAS AT MOST D ROOTS, AND SO THE ELEMENTS B, B2, , BD = ARE PRECISELY THESE ROOTS IN PARTICULAR, EVERY ELEMENT OF ORDER D IS OF THE FORM BI ON THE OTHER HAND, IT IS EASILY CHECKED THAT ORD(BI) = D (I,D), WHERE (I, D) DENOTES THE GREATEST COMMON DIVISOR OF I AND D HENCE ORD(BI) = D IF AND ONLY IF (I, D) = 1, THAT IS, IF I AND D ARE RELA- TIVELY PRIME DENOTING EULER’S FUNCTION BY ?(D) = #{I : 1 ?I ? D, (I, D) = 1}, WE THUS HAVE ?(D) = ?(D) WHENEVER ?(D) > 0 LOOKING AT (8) WE ?ND N = D|N ?(D) ? D|N ?(D) BUT, AS WE ARE GOING TO SHOW THAT D|N ?(D) = N, (9) WE MUST HAVE ?(D) = ?(D) FOR ALL D IN PARTICULAR, ?(N) = ?(N) ?1, AND SO THERE IS AN ELEMENT OF ORDER N THE FOLLOWING (FOLKLORE) PROOF OF (9) BELONGS IN THE BOOK AS WELL CONSIDER THE N FRACTIONS P ), SINCE THERE ARE EQUALLY MANY QUADRATIC RESIDUES AND NONRESIDUES PROOFS FROM THE BOOK 2 3, SINCE 1 + ? + ?2 = 0 COMPLETES THE PROOF ? REFERENCES [1] A BAKER: A CONCISE INTRODUCTION TO THE THEORY OF NUMBERS, CAMBRIDGE UNI- VERSITY PRESS, CAMBRIDGE 1984 [2] F G EISENSTEIN: GEOMETRISCHER BEWEIS DES FUNDAMENTALTHEOREMS FÜR DIE QUADRATISCHEN RESTE, J REINE ANGEWANDTE MATHEMATIK 28 (1844), 186-191 [3] C F GAUSS: THEOREMA ARITHMETICI DEMONSTRATIO NOVA, COMMENT SOC REGIAE SCI GÖTTINGEN XVI (1808), 69; WERKE II, 1-8 (CONTAINS THE 3RD PROOF) [4] C F GAUSS: THEOREMATIS FUNDAMENTALIS IN DOCTRINA DE RESIDUIS QUADRATICIS DEMONSTRATIONES ET AMPLICATIONES NOVAE (1818), WERKE II, 47-64 (CONTAINS THE 6TH PROOF) [5] F LEMMERMEYER: RECIPROCITY LAWS, SPRINGER-VERLAG, BERLIN 2000 PROOFS FROM THE BOOK THE LAW OF QUADRATIC RECIPROCITY “WHAT’S UP?” “I’M PUSHING 196 PROOFS FOR QUADRATIC RECIPROCITY” PROOFS FROM THE BOOK