6. Divisibility; ordered fields.

The elementary arithmetical operations, and especially the calculus of fractions, could not but lead to numerous empirical verifications of the divisibility of whole numbers. But neither the Babylonians (however so expert at Algebra), nor the Egyptians (in spite of their acrobatic calculations with fractions) seem to have known any general rules governing these properties, and it is to the Greeks that the initiative returns here. Their arithmetic work, of which a masterly exposition is found in Books VII and IX of Euclid [107], does not yield pride of place to any of their most beautiful discoveries in the other branches of mathematics. The existence of the H.C.D. of two integers is proved already at the beginning of Book VII by the procedure known under the name of "Euclid's algorithm";$^1$ it serves as a foundation for all ulterior developments (properties of prime numbers, existence and calculation of the L.C.M., etc.); and the crowning of the structure is formed by the two remarkable theorems proving the existence of an infinity of prime numbers (Book IX, prop. 20) and giving a procedure for constructing perfect even numbers starting with certain prime numbers (this procedure gives in fact all the even perfect numbers, as Euler was to prove). Only the existence and uniqueness of the decomposition into prime factors are not proved in a general form; all the same Euclid proves explicitly that every integer is divisible by a prime number (Book VII, prop. 31), as well as the two following propositions (Book IX, props. 13 and 14):

"If, starting from a unit, as many numbers as desired are in a progression of constant ratio [i.e. geometric], and that the one after the unit is prime, the largest will not be divisible by any except those that occur in the progression" (in other words, a power $p^n$ of a prime number can not be divided except by the powers of $p$ with exponent $\leq n$).

"If a number is the smallest that is divisible by [given] prime numbers, it will not be divisible by any other prime number with the exception of those

$^1$ If $a_1$ and $a_2$ are two integers, such that $a_1 \geq a_2$, $a_n$ is defined by induction (for $n \geq 3$) as being the remainder of the Euclidean division of $a_{n-2}$ by $a_{n-1}$; if $m$ is the least index such that $a_m = 0, a_{m-1}$ is the H.C.D. of $a_1$ and $a_2$. What we have there is the transposition to the domain of the integers of the method of successive subtractions (sometimes also called $\alpha\nu\theta\nu\phi\alpha\rho\varepsilon\sigma\iota\zeta$) for seeking the common measure of two quantities. This goes back without doubt to the Pythagoreans, and seems to have been the basis of a pre-Eudoxian theory of irrational numbers.

initially [given as] dividing if" (in other words, a product of distinct prime numbers $p_1 \ldots p_k$ has no other prime factors than $p_1, \ldots, p_k$).

It seems therefore that if Euclid does not state the general theorem it is only due to a terminology and notation adequate only for arbitrary powers of an integer.$^2$

Although a careful study makes it likely that there exists, in the text of Euclid, several successive layers, each corresponding to a stage in the development of Arithmetic,$^3$ it seems that this evolution was entirely completed between the beginning of the Vth century and the middle of the IVth, and one can only admire the shrewdness and the sure footedness of the logic that are manifested there: we must wait two millennia to take part in comparable progress in Arithmetic.

It is so-called "indeterminate" or "diophantine" problems which are at the source of the ulterior developments of Number Theory. The term "diophantine equations", as it is used today, is not, historically, completely justified; one means in general by that algebraic equations (or systems of equations) with integral coefficients, for which one is looking only for the solutions in integers: a problem that is normally impossible if the equations are "determined", that is to say have only a finite number of solutions (in real or complex numbers), but that, on the contrary, often allows solutions when there are more unknowns than equations. Yet, if Diophantus seems clearly to have been the first to have considered "indeterminate" problems, he only exceptionally looks for integral solutions, and is content most of the time with obtaining a single solution in rational numbers [91 a]. This is a type of problem that he can solve most of the time by algebraic calculations where the arithmetic nature of the unknowns does not arise;$^4$ also divisibility theory

$^2$ In support of this hypothesis, one can still remark that the proof of the theorem on perfect numbers is basically just another particular case of the theorem on the unique decomposition into prime factors. Besides, all the testimonies concur to show that from this period the decomposition of a number explicitly into prime factors was known and currently used; but a complete proof is not found for the decomposition theorem before that given by Gauss at the beginning of the Disquisitiones ([124 a], v. I, p. 15).

$^3$ Cf. [317 d]. An example of the residue of an earlier version is furnished by props. 21 to 34 of Book IX, which deal with the most elementary properties of divisibility by 2, and go back no doubt to a period when the general theory of prime numbers was not yet developed. It is known besides that the categories of Even and Odd played a big role in the philosophico-mythical speculations of the first Pythagoreans, to whom it is natural to try to make this fragment go back (cf. [17 b]).

$^4$ If Diophantus, in indeterminate problems, always returns to problems in a single unknown, by means of a numerical choice for the other unknowns which makes his final equation possible, it appears fully that this method is due mostly to his notation which did not allow him to calculate with several unknowns at once; in any case, he does not lose sight, during the calculations, of the numerical substitutions that he has made, and modifies them, if need be, if they are not suitable, by writing down a compatibility condition for the substituted variables, and in solving this auxiliary problem first. In other words, he handles these substituted numerical only plays a very retiring role (the word prime number is only pronounced a single time ([91 a], Book V, problem 9, v. I, pp. 334-335), and the notion of relatively prime numbers is only brought up in connection with the theorem affirming that the quotient of two relatively prime numbers can not be a square unless each of them is a square).$^5$

The study of integral solutions of indeterminate equations does not really start until the Chinese and Hindu mathematicians of the high Middle Ages. The first of these seem to have been led to speculations of this kind by practical problems in the making of calendars (where the determination of periods common to several cycles of astronomical phenomena constituted precisely a "diophantine" problem of the first degree); to them is owed in any case (no doubt between the IVth and the VIIth century of our era) a rule for the solution of simultaneous linear congruences. As for the Hindus, of whom the mathematics knew its full flowering from the Vth to the XIIIth century, not only did they know how to treat methodically (by the application of Euclid's algorithm) systems of linear diophantine equations with an arbitrary number of unknowns,$^6$ but they are the first to tackle and solve problems of the second degree, including certain particular cases of "Fermat's equation" $Nx^2 + 1 = y^2$ ([78], vol. II, pp. 87-307).

We do not need to pursue here the history of the theory of diophantine equations of degree > 1, which, following on from the work of Fermat, Euler, Lagrange and Gauss, was to end up in the XIXth century with the theory of algebraic integers (cf. pp. 93 ff.). As we have already noted (cf. p. 58), the study of linear systems, which seems no longer to present problems worthy of interest, is somewhat neglected during this period: in particular, general necessary conditions for solutions of an arbitrary system are not sought, nor is the description of the set of solutions. However, towards the middle of the XIXth century, Hermite is led to use, in connection with his research in Number Theory, several lemmas about linear Diophantine equations, and notably a "reduced form" for a linear substitution with integral coefficients ([159], v. I, pp. 164 and 265); finally, after Heger had given in 1858 the necessary condition for a system whose rank is equal to the number of equations, H. J. Smith, in 1861, defines the invariant factors of a matrix with integral entries in a "canonical form" ([287], v. I, pp. 367-409).

But in the interval the notion of an abelian group was gradually becoming more precise, following its introduction by Gauss (cf. p. 60), and so was

$^5$ Different indices testify however to a more advanced knowledge of arithmetic with Diophantus: he knows for example that the equation $x^2 + y^2 = n$ has no rational solutions if $n$ is an integer of the form $4k + 3$ (Book V, problem 9 and Book VI, problem 14 ([91 a], v. I, pp. 332-335 and p. 425; cf. also [153 f], pp. 105-110)). $^6$ Astronomical problems were also among those that led the Hindus to concern themselves with this type of equation (cf. [78], v. II, pp. 100, 117 and 135).

the importance taken by this notion in the ulterior development of Number Theory. In the particularly deep study, expounded in the Disquisitiones, of the finite abelian group of classes of quadratic forms of a given discriminant, Gauss rapidly realised that certain of these groups were not cyclic: "in this case", he says, "a basis [that is to say a generator] is not sufficient, two, or a greater number, must be taken, which, by multiplication and composition,$^7$ will be able to produce all the classes" ([124 a], v. I, pp. 374-375). It is not certain that, with these words, Gauss wished to describe the decomposition of a group as a direct product of cyclic groups; however, in the same page in the Disquisitiones, he proves that there exists an element in the group whose order is the L.C.M. of the orders of all the elements — in other words, he obtains the existence of the largest invariant factor of the group ([124 a], v. I, p. 373) —; and on the other hand, the notion of direct product was known to him, for in a manuscript dating from 1801 but not published during his lifetime, he sketches a general proof of the decomposition of a finite abelian group as a direct product of $p$-groups$^8$ ([124 a], v. II, p. 266). In any case, in 1868, Schering, the editor of Gauss's work, inspired by these results (and notably by this manuscript that he had just found again) proves (still for the group of classes of quadratic forms) the general decomposition theorem ([272], v. I, pp. 135-148) by a method which, taken up again two years later in abstract terms by Kronecker ([186 a], v. I, pp. 273-282), is essentially that which is still used today. As for torsion-free abelian groups, we have already said (cf. pp. 64 ff.) how the theory of elliptic functions and abelian integrals, developed by Gauss, Abel and Jacobi, led little by little to take note of their structure; the first and most famous example of the decomposition of an infinite group as a direct sum of monogenic groups is given by Dirichlet in 1846 in his memoir on the units of an algebraic number field ([92], v. I, pp. 619-644). But it is only in 1879 that the link between the theory of abelian groups of finite type and the theorem of Smith is recognised and used explicitly by Frobenius and Stickelberger ([120], )

At about the same time the theory of similarity for matrices (with real or complex coefficients) was being completed. The notion of eigenvalue of a linear substitution appears explicitly in the theory of systems of linear differential equations with constant coefficients, applied by Lagrange ([191], v. I, p. 520) to the theory of small movements, by Lagrange ([191], v. VI, pp. 655-666) and Laplace ([193], v. VIII, pp. 325-366) to the "secular" inequalities of the planets. It is implicit in many other problems tackled about the middle of the XVIIIth century, such as the determination of the axes of a conic or a quadric (accomplished first by Euler ([108 a], (1), v. IX, p. 384)), or the study (developed also by Euler ([108 a], (2), v. III, pp. 200-201)) of the principal

$^7$ Gauss denotes the law of composition of classes additively, by "multiplication" he means thus the product of a class with an integer.

$^8$ Abel also proves in passing this property in his memoir on abelian equations ([1], v. I, pp. 494-497).

axes of inertia of a solid body (discovered by De Segner in 1755); we know today that it is she also who (in a much more hidden form) took part in the beginnings of the theory of partial differential equations, and in particular in the equation of vibrating strings. But (without talking of this latter case) the common ancestry between these various problems is hardly recognised before Cauchy ([56 a], (2), v. V, p. 248 and v. IX, p. 174). Further, as the majority bring in symmetric matrices, it is the eigenvalues of these latter which are mostly studied at first; let us note here that from 1826, Cauchy proves the invariance under similarity of the eigenvalues of these matrices, and proves that they are real for a symmetric matrix of order 3 ([56 a], (2), v. V, p. 248), a result that he generalises to arbitrary real symmetric matrices three years later ([56 a], (2), v. IX, p. 174).9 The general notion of projectivity, introduced by Möbius in 1827 ([223], v. I, p. 217), arrives quickly at the problem of classification of these transformations (in 2 and 3 dimensions first of all), which is none other than the problem of the similarity of the corresponding matrices; but for a long time this question is only treated by the "synthetic" methods which are in vogue in the middle of the XIXth century, and its progress (in any case fairly slow) does not seem to have had any influence on the theory of eigenvalues. It is not the same with another problem from geometry, the classification of pencils of conics or quadrics, which from the modern point of view, reduces to the study of elementary divisors of the matrix $U + \lambda V$ where $U$ and $V$ are two symmetric matrices; it is exactly in this vein that Sylvester, in 1851, tackles this problem, examining with care (with the aim of finding "canonical forms" for the pencil under consideration) what becomes of the minors of the matrix $U + \lambda V$ when a value is substituted for $\lambda$ which annihilates its determinant ([304], v. I, pp. 219-240). The purely algebraic aspect of the theory of eigenvalues progresses simultaneously; it is thus that several authors (among whom Sylvester himself) prove around 1850 that the eigenvalues of $U^n$ are the $n$th powers of the eigenvalues of $U$, whereas in 1858 Cayley, in the memoir in which he sets up the calculus of matrices ([58], v. II, pp. 475-496), states the "Cayley-Hamilton theorem" for a square matrix of arbitrary order,10 contenting himself with proving it by direct calculation for matrices of order 2 and 3. Finally, in 1868, Weierstrass, taking up again the method of Sylvester, obtains "canonical forms" for a "pencil" $U + \lambda V$, where, this time, $U$ and $V$ are square matrices which are not necessarily symmetric, subject only to the condition that $\det(U + \gamma V)$

9 An attempt at a proof of this result, for the particular case of the "secular" inequalities of the planets, had already been made in 1784 by Laplace ([193], v. IX, pp. 49-92). As far as the equation of degree 3 is concerned giving the axes of a real quadric, Euler had stated without proof the real character of its roots, and an attempt to prove it by Lagrange, in 1773 ([191], v. III, pp. 579-616) is insufficient; this point was proved rigorously for the first time by Hachette and Poisson in 1801 [140]. 10 Hamilton had incidentally proved this theorem for matrices of order 3 a few years earlier ([145 a], pp. 566-567).

is not identically null; he deduces from this the definition of the elementary divisors of an arbitrary square matrix (with complex entries), and proves that they characterise this latter up to similarity ([329 a], v. II, pp. 19-44); these results are besides found again partially (and apparently independently) by Jordan two years later$^{11}$ ([174 a], pp. 114-125). Here again, it is Frobenius who, in 1879, shows that the theorem of Weierstrass can be easily deduced from the theory of Smith, extended to polynomials ([119], v. I, pp. 482-544, )

We have just alluded to the theory of divisibility of polynomials in one variable; the question of the division of polynomials was naturally to be stated from the beginning of algebra, as the inverse of the operation of multiplication (this latter being already known to Diophantus, at least for polynomials of small degree); but it can be conceived that it is hardly possible to tackle the problem in a general way before a coherent notation for the various powers of the variable was imposed. In fact, examples of the process of "Euclidean" division of polynomials, such as we know it, are hard to find before the middle of the XVIth century;$^{12}$ and S. Stévin (who essentially uses exponent notation) seems to be the first to have the idea of deducing from it the extension of "Euclid's algorithm" for the determination of the G.C.D. of two polynomials ([295], v. I, pp. 54-56). Taking that into account, the notion of divisibility remained peculiar to rational integers until the middle of the XVIIth century. It is Euler who, in 1770, opens a new chapter of Arithmetic by extending, not without temerity, the notion of divisibility to integers in a quadratic extension: seeking to determine the divisors of a number of the form $x^2 + cy^2$ ($x, y, c$ rational integers), he writes $x + y\sqrt{-c} = (p + q\sqrt{-c})(r + s\sqrt{-c})$ ($p, q, r, s$ rational integers) and taking the norms of both members, he does not hesitate to affirm that he obtains in this way all the divisors of $x^2 + cy^2$ in the form $p^2 + cq^2$ ([108 a], (1), v. I, p. 422). In other words, Euler argues as if the ring $\mathbf{Z}[\sqrt{-c}]$ were principal; a little later, he uses an analogous argument to apply the method of "infinite descent" to the equation $x^3 + y^3 = z^3$ (it reduces to writing that $p^2 + 3q^2$ is a cube, which he does by stating $p + q\sqrt{-3} = (r + s\sqrt{-3})^3$). But from 1773, Lagrange proves ([191], v. III, pp. 695-795) that the divisors of numbers of the form $x^2 + cy^2$ are not always of this form, the first example of the fundamental difficulty which was to occur with much greater clarity in the studies, taken up by Gauss and his successors, on divisibility in the fields of roots of unity;$^{13}$ it is not possible in

$^{11}$ Jordan does not mention the invariance of the canonical form that he obtains. It is interesting to observe elsewhere that he deals with this question, not for matrices with complex entries, but for matrices over a finite field. Let us note on the other hand that, from 1862, Grassmann had given a method for reducing a matrix (with complex entries) to triangular form, and mentioned explicitly the link between this reduction and the classification of projectivities ([134], v. I₂, pp. 249-254). $^{12}$ Cf. for example [33]. $^{13}$ Gauss seems for a moment to have hoped that the ring of integers in the field of $n$th roots of unity was a principal ideal ring; in a manuscript unpublished during his general to extend directly to these fields the essential divisibility properties of rational integers, the existence of the G.C.D. and the uniqueness of the decomposition into prime factors. It is not the place here to describe in detail how Kummer for the field of roots of unity [188 b],$^{14}$ then Dedekind and Kronecker for arbitrary fields of algebraic numbers, succeed in surmounting this formidable obstacle by the creation of the theory of ideals, one of the most decisive advances of modern algebra (cf. pp. 93 ff.). But Dedekind, always curious about the foundations of the various mathematical theories, is not content with this success; and, analysing the mechanism of the relations of divisibility, he sets up the basis of the modern theory of ordered groups, in a memoir (without stirring his contemporaries, and forgotten for 30 years) which is without doubt one of the first by date of the works on axiomatic algebra ([79, v. II, pp. 103-147]).

From the middle of XVIIIth century, the search for a proof of the "fundamental theorem of algebra" is the order of the day (cf. p. 74). We do not need to remember here the attempt by d'Alembert, who inaugurated the series of proofs using the infinitesimal calculus (cf. p. 161). But, in 1749, Euler tackles the problem in another way ([108 a], (1), v. VI, pp. 78-147): for every polynomial $f$ with real coefficients, he seeks to prove the existence of a decomposition $f = f_1 f_2$ into two polynomials (not constants) with real coefficients, which would give him a proof of the "fundamental theorem" by induction on the degree of $f$. It is sufficient even, as he remarks, to stop with the first factor of odd degree, and in consequence all the difficulties reduce to considering the case where the degree $n$ of $f$ is even. Euler limits himself then to the study of the case where the desired factors are both of degree $n/2$, and he indicates that, by an elimination calculation suitably undertaken, the unknown coefficients of $f_1$ and $f_2$ can be expressed rationally in terms of a root of an equation with real coefficients of which the extreme terms are of opposite signs and which as a consequence has at least one real root. But Euler's proof is only a sketch, where a number of essential points are passed over in silence; and it is only in 1772 that Lagrange succeeds in solving the difficulties raised by this proof ([191], v. III, pp. 479-516) by means of a very long and very meticulous analysis, where he proves himself capable of lifetime ([124 a], v. II, pp. 387-397), he is seen proving the existence of a procedure of Euclidean division in the field of cube roots of unity, and giving some indications for an analogous procedure in the field of 5th roots; he uses these results to prove by an argument of "infinite descent" more correct than that of Euler the impossibility of the equation $x^3 + y^3 = z^3$ in the field of cube roots of unity, points out that the method can be extended to the equation $x^5 + y^5 = z^5$, but stops at the equation $x^7 + y^7 = z^7$ in recording that then it is impossible to reject a priori the case where $x, y, z$ are not divisible by 7.

$^{14}$ From his first work on "ideal numbers", Kummer sets out explicitly the possibility of applying his method, not only to fields of roots of unity, but also to quadratic fields, and to find again thus the results of Gauss on binary quadratic forms ([188 b], pp. 324-325).

a remarkable virtuosity in the use of "Galois" methods (so to speak) newly created by him (cf. pp. 75 ff.).

All the same Lagrange, like Euler and all his contemporaries, does not hesitate to argue formally in a "field of roots" of a polynomial (that is to say, in his language, to consider "imaginary roots" of this polynomial); the Mathematics of his time had not supplied any justification for this type of argument. Also Gauss, deliberately hostile, from its beginnings, to the frantic formalism of the XVIIIth century, raises himself powerfully, in his dissertation, against this abuse ([124 a], v. III, p. 3). But he would not have been himself if he had not felt that it was a case there of an argument with a defective presentation that was intrinsically correct. Also we see him, a few years later ([124 a], v. III, p. 33; cf. also [124 b]) taking up again a simpler variant of Euler's argument, suggested already in 1759 by de Foncenex (but that this latter was not able to bring to a satisfactory end), and deducing from it a new proof of the "fundamental theorem", where he avoids carefully all use of "imaginary" roots: these last being replaced by clever adjunctions and specialisations of indeterminates.

The role of Topology in the "fundamental theorem" is thus reduced to the one theorem according to which a polynomial with real coefficients can not change sign in an interval without becoming zero (Bolzano's theorem for polynomials). This theorem is also at the bottom of all the separation criteria for real roots of a polynomial (with real coefficients), which constitute one of the favourite subjects of Algebra during the XIXth century.$^{15}$

During this research, one could not fail to notice that it is the order structure of $\mathbf{R}$, even more than its topology, that plays there the essential role;$^{16}$ for example, Bolzano's theorem for polynomials is still true for the field of all real algebraic numbers. This movement of ideas found its goal in the abstract theory of ordered fields, created by E. Artin and O. Schreier ([7 b] and [8 a and b]); one of its more remarkable results is no doubt the discovery that the existence of an order relation on a field is linked to purely algebraic properties of the field.

$^{15}$ On these questions, the reader could for example consult [284] or [317 a], pp. 223-235.

$^{16}$ The tendency to attribute to the order structure of the real numbers a preponderant place is also prominent in the definition of real numbers in the procedure of Dedekind "cuts", which is fundamentally a procedure applicable to all ordered sets.