34 The Theory of Numbers in the Nineteenth Century It is true that Fourier had the opinion that the principal object of mathematics was public use and the explanation of natural phen mena but a philosopher like him ought to know that the sole object of the science is the honor of the human spirit and that under this view a problem of [the theory of]numbers is worth as much as a problem on the system of the world. C.G.J.JACOBI 1.Introduction Up to the nineteenth century the theory of numbers was a series of isolated though often brilliant results.A new era began with Gauss's Disquisitiones Arithmeticae1 which he composed at the age of twenty.This great work had been sent to the French Academy in 1800 and was rejected but Gauss published it on his own.In this book he standardized the notation;he systematized the existing theory and extended it;and he classified the problems to be studied and the known methods of attack and introduced new methods.In Gauss's work on the theory of numbers there are three main ideas:the theory of congruences,the introduction of algebraic numbers,and the theory offorms as the leading idea in Diophantine analysis.This work not only began the modern theory of numbers but determined the directions of work in the subject up to the present time.The Disquisitiones is difficult to read but Dirichlet expounded it. Another major nineteenth-century development is analytic number theory,which uses analysis in addition to algebra to treat problems involving the integers.The leaders in this innovation were Dirichlet and Riemann. 2.The Theory of Congruences Though the notion of congruence did not originate with Gauss-it appears in the work of Euler,Lagrange,and Legendre-Gauss introduced the notation 1.Published 1801 =Werke,1. 813
814 THE THEORY OF NUMBERS 1800-1900 in the first section of Disquisitiones and used it systematically thereafter.The basic idea is simple.The number 27 is congruent to 3 modulo 4, 27 =3 modulo 4, because 27-3 is exactly divisible by 4.(The word modulo is often ab breviated to mod.)In general,if a,b,and m are integers a≡b modulo m if a-b is (exactly)divisible by m or if a and b have the same remainders on division by m.Then b is said to be a residue of a modulo m and a is a residuc of b modulo m.As Gauss shows,all the residues of a modulo m,for fixed a and lm,are given by a+km where k=0,±l,±2， Congruences with respect to the same modulus can be treated to some extent like cquations.Such congruences can be added,subtracted,and multiplied.One can also ask for the solution of congruences involving unknowns.Thus,what values of x satisfy 2x 25 modulo 12? This equation has no solutions because 2x is even and 2x-25 is odd.Hence 2x-25 cannot be a multiple of 12.The basic theorem on polynomial yedy en Ax+Bx-1+··+Mx+N=0 modulo p whose modulus is a prime number p which does not divide A cannot have more than n noncongruent roots. In the third section Gauss takes up residues of powers.Here he gives a tme f onmeot f tm a-1≡1 modulop. The theorem follows from his study of congruences of higher degree,namely, ≡a modulo m where a and m are relatively prime.This subject was continued by many men after Gauss. The fourth sctioof Disgreats qudratic reidues.Ifisa prime and a is not a multiple of and if there exists an x such that a mod,then a is a quadratic residue of;otherwise a is a quadratic non- residue of.After proving som subordinate theoremson quadratic residues Gauss gave the first rigorous proof of the law of quadratic reciprocity(Chap. 2.Hit.kl'4ad.de Berlin,24,1768,192,pub.1770=Ewr,2,655-726
THE THEORY OF CONGRUENCES 815 25,sec.4).Euler had given a complete statement much like Gauss's in one paper of his Opuscula Analytica of 783 (Chap.25,sec.4).Nevertheless in article 151 of his Disquisitiones Gauss says that no one had presented the theorem in as simple a form as he had.He refers to other work of Euler including another paper in the Opuscula and to Legendre's work of 1785 Of these papers Gauss says rightly that the proofs were incomplete. Gauss is supposed to have discovered a proof of the law in 1796 when he was nineteen.He gave another proofin the Disquisitiones and later published four others.Among his unpublished papers two more were found.Gauss says that he sought many proofs because he wished to find one that could be used to establish the biquadratic reciprocity theorem (see below).The law of quadratic reciprocity,which Gauss called the gem of arithmetic,is a basic result on congruences.After Gauss gave his proofs,more than fifty others were given by later mathematicians Gauss also treated congruences of polynomials.If 4 and B are two polynomials in x with,say,real coefficients then one knows that one can find unique polynomials Q and R such that A=B.Q+R, where the degree of R is less than the degree of B.One can then say that two polynomials A and A2 are congruent modulo a third polynomial P if they have the same remainder R on division by P. Cauchy used this idea3 to define complex numbers by polynomial congruences.Thus if f(x)is a polynomial with real coefficients then under division by x+1 f(x)≡a+bx modx2+1 because the remainder is of lower degree than the divisor.Here a and b are necessarily real by virtue of the division process.If g(x)is another such polynomial then g(x≡c+dx mod2+1. Cauchy now points out that if A1,A2,and B are any polynomials and if A1 BQ1 R1 and A2 BQ2 R2 then A1+A2=R1 R2 mod B,and A142=RR2 mod B. We can now see readily that f(x)+g(x)(a +c)+(b +d)x mod x2+1 3.Exercices d'analyse et de physique mathimatique,4,1847,84.=Eupres,(1,10,312-23 and (2),14,93-120
816 THE THEORY OF NUMBERS 1800-1900 and since x2-I mod x2+1 that f(x)g(x)=(ac-bd)+(ad +bc)x mod x2 +1. Thus the numbers a +bx and c+dx combine like complex numbers;that is, they have the formal properties of complex numbers,x taking the place of i. Cauchy also proved that every polynomial g(x)not congruent to 0 modulo 2+1 has an inverse,that is,a polynomial h(x)such that h(x)g(x)is congruent to 1 modulo x2 +1. Cauchy did introduce i for x,i being for him a real indeterminate quantity.He then showed that for any f(i)=a0+a1i+a22+. that f(i)≡a0-a2+a4-.+(a1-a3+a5-.)i modulo i2+1 Hence any expression involving complex numbers behaves as one of the form c+di and one has all the apparatus needed to work with complex expressions.For Cauchy,then,the polynomials in i,with his understanding about i,take the place of complex numbers and one can put into one class all those polynomials having the same residue modulo i2+1.These classes are the complex numbers. It is interesting that in 1847 Cauchy still had misgivings about v-1 He says,"In the theory of algebraic equivalences substituted for the theory ofimaginary numbers the lettericeases to represent the symbolic sign which we repudiate completely and which we can abandon without regret since one does not know what this supposed sign signifies nor what sense to attribute to it.On the contrary we represent by the letter i a real quantity but indeterminate and in substituting the sign for =we transform what has been called an imaginary equation into an algcbraic equivalence relative to the variable i and to the divisor i2+1.Since this divisor remains the same in all the formulas one can dispense with writing it." In the second decade of the century Gauss proceeded to search for reciprocity laws applicable to congruences of higher degree.These laws again involve residues of congruences.Thus for the congruence x4≡g modp one can define g as a biquadratic residue ofp if therc is an integral value of x satisfying the equation.He did arrive at a law of biquadratic reciprocity (see below)and a law of cubic reciprocity.Much of this work appeared in papers from 1808 to 1817 and the thcorem proper on biquadratic residues vas given in papers of 1828 and 1832. 4.Comm.Soc.Got,6,1828,and7,1832=Werke,2,65-92and93-148;also pp.165-78
THE THEORY OF CONGRUENCES 817 To attain elegance and simplicity in his theory of cubic and biquadratic residues Gauss made use of complex integers,that is,numbers of the form a+bi with a and b integral or 0.In Gauss's work on biquadratic residues it was necessary to consider the case where the modulus b is a prime of the form 4n+1 and Gauss needed the complex factors into which prime numbers of the form 4n +1 can be decomposed.To obtain these Gauss realized that one must go beyond the domain of the ordinary integers to introduce the complex integers.Though Euler and Lagrange had introduced such integers into the theory of numbers it was Gauss who established their importance Whereas in the ordinary theory of integers the units are +1 and -I in Gauss's theory of complex integers the units are tl and ti.A complex integer is called composite if it is the product of two such integers neither of which is a unit.If such a decomposition is not possible the integer is called a prime.Thus 5 =(1 2i)(1-2i)and so is composite,whereas 3 is a complex prime. Gauss showed that complex integers have essentially the same properties as ordinary integers.Euclid had proved (Chap.4,sec.7)that every integer is uniquely decomposable into a product of primes.Gauss proved that this unique decomposition,which is often referred to as the fundamental theorem of arithmetic,holds also for complex integers provided we do not regard the four unit numbers as different factors.That is,if a =bc =(ib)(-ic),the two decompositions are the same.Gauss also showed that Euclid's process for finding the greatest common divisor of two integers is applicable to the complex integers. Many theorems for ordinary primes carry over to the complex primes. Thus Fermat's theorem carries over in the form:If be a complex prime a bi and k any complex integer not divisible by b then kNp-1≡】modulo where No is the norm (a2+b2)of b.There is also a law of quadratic reciprocity for complex integers,which was stated by Gauss in his 1828 paper. In terms of complex integers Gauss was able to state the law of bi- quadratic reciprocity rather simply.One defines an uneven integer as one not divisible by 1 +i.A primary uneven integer is an uneven integer a bi such that b is even and a+b I is even.Thus -7 and-5 2i are primary uneven numbers.The law of reciprocity for biquadratic residues states that if o and B are two primary uneven primes and A and B are their norms,then 。=(-1ae-a-