Translation:Disquisitiones Arithmeticae/Second Section

Article 13

Template:Sc The product of two positive numbers, each of which is smaller than a given prime, cannot be divisible by this prime.

Let $p$ be the prime, and let $a$ be a positive number $<p:$ then it is not possible to find a number $b,$ smaller than $p,$ such that $ab\equiv 0(\mathrm{mod}p).$

Proof. If anyone denies it, let us suppose that numbers $b,$ $c,$ $d$ etc. are given, all of which are less than $p,$ such that $ab\equiv 0(\mathrm{mod}p),$ $ac\equiv 0(\mathrm{mod}p)$ etc. Let $b$ be the smallest of these, so that all numbers smaller than $b$ are deprived of this property. Clearly $b>1,$ for if $b=1,$ then we would have $ab=a<p,$ so $ab$ would not be divisible by $p.$ Now, as a prime number, $p$ cannot be divisible by $b,$ and must instead fall between two multiples of $b,mb$ and $(m+1)b.$ Let $p-mb=b^{\prime }.$ Then $b^{\prime }$ will be positive and $<b.$ Since we have assumed $ab\equiv 0(\mathrm{mod}p),$ it is also true that $mab\equiv 0$ (Art. [[../First_Section#Article_7|7]]), and hence subtracting from $ap\equiv 0$ we will have $a(p-mb)=a{b}^{\prime }\equiv 0$; i.e. $b^{\prime }$ is included among the numbers $b,$ $c,$ $d$ etc., even though $b$ was supposed to be the smallest of them. Q.E.A.

Article 14

If neither $a$ nor $b$ is divisible by a given prime number $p,$ then the product $ab$ will also not be divisible by $p$.

Let $\alpha$ and $\beta$ be the minimal positive residues of the numbers $a$ and $b$ modulo $p.$ By hypothesis, neither of these will be zero. Now, if it were true that $ab\equiv 0(\mathrm{mod}p),$ then since $ab\equiv \alpha \beta ,$ it would also be true that $\alpha \beta \equiv 0.$ But this is impossible, by the previous theorem.

The proof of this theorem has already been given by Euclid, Elements, vii, 32. However, we did not want to omit it, both because several modern authors have presented vague reasoning instead of a proof, or have neglected this theorem; and also because the nature of the method used here, which we will later apply to much more difficult problems, can be more easily understood from a simpler case.

Article 15

If none of the numbers $a,b,c,d,\dots$ is divisible by the prime number $p,$ then the product $abcd$ etc. will also not be divisible by $p$.

According to the previous article, $ab$ is not divisible by $p,$ so the same is true for $abc,$ hence also for $abcd,$ etc.

Article 16

Template:Sc A composite number can only be resolved into prime factors in one way.

Proof. It is evident from first principles that any number can always be decomposed into prime factors; but it is often tacitly assumed that this decomposition is only possible in one way. Let us imagine a composite number $A=a^{\alpha }{b}^{\beta }{c}^{\gamma }$ etc., where $a,$ $b,$ $c$ etc. are unequal prime numbers, and suppose that $A$ can be resolved into prime factors in yet another way. It is first of all clear that in this second system of factors, primes other than $a,$ $b,$ $c$ etc. cannot enter, since these are the only primes which divide $A$. Similarly, none of the prime numbers $a,$ $b,$ $c$ etc. can be missing, because if that were the case, the missing primes would not divide $A$ (Art. 15); thus the two factorizations can only differ insofar as a prime is repeated more times in one than in the other. Let $p$ be a prime number, which is repeated $m$ times in one system and $n$ times in the other, with $m>n$. Now let the factor $p$ be removed from each system $n$ times, so that it remains in one system $m-n$ times, and has disappeared from the other. Then the number $\frac{A}{p^n}$ has two different factorizations, one of which is completely free of the factor $p$, while the other still contains it $m-n$ times, contrary to what we have just shown.

Article 17

Therefore, if a composite number $A$ is the product of $B,$ $C,$ $D$ etc., then it is clear that the numbers $B,$ $C,$ $D$ etc. cannot have prime factors different from those of $A,$ and that each of these factors must occur as many times altogether in the numbers $B,$ $C,$ $D$ etc. as it does in $A.$ From this, one obtains a criterion to determine whether one number $B$ divides another number $A.$ This will happen if $B$ does not involve any prime more times than $A;$ if this condition is not satisfied, then $B$ will not divide $A.$

With the help of the calculus of combinations, it is easy to see that if $A=a^{\alpha }{b}^{\beta }{c}^{\gamma }$ etc., where as above $a,$ $b,$ $c$ etc. denote distinct prime numbers, then $A$ has

$$(\alpha +1)(\beta +1)(\gamma +1)\dots$$

distinct divisors, including $1$ and $A.$

Article 18

It is therefore clear that if $A=a^{\alpha }{b}^{\beta }{c}^{\gamma }$ etc., $K=k^{\kappa }{l}^{\lambda }{m}^{\mu }$ etc., and if the primes $a,$ $b,$ $c$ etc., $k,$ $l,$ $m$ etc. are all distinct from one another, then $A$ and $K$ will have no common divisor other than $1,$ or in other words they will be relatively prime.

Given several numbers $A,$ $B,$ $C$ etc., their greatest common divisor is determined as follows. The numbers are resolved into their prime factors, and those that are common to all the numbers $A,$ $B,$ $C$ etc. are taken (if there are none, the given numbers would have no common divisor). Then one notes how many times each of these prime factors is contained in $A,$ $B,$ $C,$ etc., or equivalently the exponents of these factor in each of the numbers $A,$ $B,$ $C,$ etc. Then each factor is given the smallest of the exponents that it has in $A,$ $B,$ $C,$ etc. Finally, the product of the resulting powers is computed; this will be the greatest common divisor.

On the other hand, if the least common multiple of the numbers $A,$ $B,$ $C,$ etc. is desired, one can proceed as follows. Collect all the prime numbers that divide any of the numbers $A,$ $B,$ $C,$ etc., and assign to each of them the largest exponent that it has in the numbers $A,$ $B,$ $C,$ etc. The product of all these powers will be the required common multiple.

Ex. Let $A=504=2^3{3}^{2}7,$ $B=2880=2^6{3}^{2}5,$ $C=864=2^5{3}^3$. To find the greatest common divisor, the prime factors $2$ and $3$ which must be assigned exponents $3$ and $2;$ this gives the greatest common divisor $2^3{3}^2=72;$ the least common multiple will be $2^6{3}^{3}5.7=60480.$

We omit the proofs because of their simplicity; after all, it is known how to solve these problems in an elementary way, even when the factorizations of the numbers $A,$ $B,$ $C,$ etc. are not given.

Article 19

If the numbers $a,$ $b,$ $c$ etc. are relatively prime to $k,$ then their product will also be relatively prime to $k.$

Indeed, because none of the numbers $a,$ $b,$ $c$ etc. has prime factors in common with $k,$ the product $abc$ etc. cannot have prime factors that do not belong to any of $a,$ $b,$ $c$ etc. Thus from the previous article, $abc$ etc. will be relatively prime to $k.$

If the numbers $a,$ $b,$ $c$ etc. are relatively prime to each other, and $k$ is divisible by each of them, then $k$ is also divisible by their product.

This is easily derived from Arts. 17 and 18. Let $p$ be any prime divisor of the product $abc$ etc., which is repeated $\pi$ times. Then it is clear that one of the numbers $a,$ $b,$ $c$ etc. will be divisible by $p^{\pi },$ and consequently $k,$ which is divisible by this number, will also be divisible by $p^{\pi }$. The same reasoning holds for the remaining divisors of the product $abc$ etc.

Therefore, if two numbers $m,$ $n$ are congruent modulo several relatively prime moduli $a,$ $b,$ $c$ etc. then they will also be congruent modulo the product. Indeed, since $m-n$ is divisible by each of the numbers $a,$ $b,$ $c$ etc., it must also be divisible by their product.

Finally, if $a$ is relatively prime to $b,$ and $ak$ is divisible by $b,$ then $k$ will also be divisible by $b.$ Indeed, since $ak$ is divisible by $a$ and $b,$ it will be divisible by their product, i.e. $\frac{ak}{ab}=\frac{k}{b}$ will be an integer.

Article 20

If $A=a^{\alpha }{b}^{\beta }{c}^{\gamma }$ etc., where $a,$ $b,$ $c$ etc. are distinct prime numbers, and $A$ is equal to a perfect power $k^n,$ then all of the exponents $\alpha ,$ $\beta ,$ $\gamma ,$ etc. will be divisible by $n.$

The number $k$ does not involve prime numbers other than $a,$ $b,$ $c$ etc. Let ${\alpha }^{\prime }$ be the exponent of $a$ in $k.$ Then $k^n$ will contain this factor $n{\alpha }^{\prime }$ times, so $n{\alpha }^{\prime }=\alpha$ and $\frac{\alpha }{n}$ is an integer. It can be shown in a similar way that $\frac{\beta }{n}$ etc. are integers.

Article 21

If $a,$ $b,$ $c$ etc. are relatively prime to each other, and their product $abc$ etc. is a perfect power $k^n,$ then each number $a,$ $b,$ $c$ etc. will also be an $n$^th power.

Let $a=l^{\lambda }{m}^{\mu }{p}^{\pi }$ etc., where $l,$ $m,$ $p$ etc. are distinct prime numbers, none of which (by hypothesis) divide any of the numbers $b,$ $c$ etc. Then the product $abc$ etc. will include $l$ as a factor $\lambda$ times, $m$ as a factor $\mu$ times, etc.: hence (by the previous article) $\lambda ,$ $\mu ,$ $\pi$ will all be divisible by $n,$ and therefore

$$\sqrt[n]{a}=l^{\frac{\lambda }{n}}{m}^{\frac{\mu }{n}}{p}^{\frac{\pi }{n}}$$

will be an integer. The same will be true for $b,$ $c$ etc.

These facts about prime numbers having been put forth, we now turn to other things which will lead us more directly to our goal.

Article 22

If the numbers $a$ and $b$ are divisible by $k,$ and are congruent with respect to a modulus $m$ that is relatively prime to $k,$ then $\frac{a}{k}$ and $\frac{b}{k}$ are congruent with respect to that same modulus.

It is clear that $a-b$ is divisible by $k,$ and also by $m$ (by hypothesis); thus $\frac{a-b}{k}$ will be divisible by $m$ (Art. 19), i.e. $\frac{a}{k}\equiv \frac{b}{k}(\mathrm{mod}m).$

If the numbers $m$ and $k$ instead have a common divisor $e,$ then we will have $\frac{a}{k}\equiv \frac{b}{k}(\mathrm{mod}\frac{m}{e})$. For $\frac{k}{e}$ and $\frac{m}{e}$ are relatively prime, and $a-b$ is divisible by $k$ and by $m,$ so $\frac{a-b}{e}$ is divisible by $\frac{k}{e}$ and by $\frac{m}{e}$ and therefore by $\frac{mk}{e^2},$ i.e. $\frac{a-b}{k}$ is divisible by $\frac{m}{e},$ or equivalently $\frac{a}{k}\equiv \frac{b}{k}(\mathrm{mod}\frac{m}{e}).$

Article 23

If numbers $a$ and $m$ are relatively prime, and numbers $e$ and $f$ are incongruent modulo $m,$ then $ae$ and $af$ will also be incongruent modulo $m$.

This is a restatement of the theorem of the preceding article.

Hence it is clear that if we multiply all of the integers from $0$ to $m-1$ by $a$, and reduce these products to their minimal residues modulo $m,$ the resulting residues will all be distinct. Since the number of these residues is $m,$ and none of them is $>m,$ it is also clear that every integer in the series from $0$ to $m-1$ will be found among them.

Article 24

The expression $ax+b,$ in which $a$ and $b$ are given numbers and $x$ is an indeterminate or variable number, can be made congruent to any given number modulo $m,$ provided that $m$ is relatively prime to $a.$

Let $c$ be the number to which it must be congruent, and let $e$ the minimal positive residue of $c-b.$ By the preceding article, it is possible to find a value $x<m$ such that the minimal residue of the product $ax$ modulo $m$ is equal to $e;$ let $v$ be this value. Then $av\equiv e\equiv c-b,$ thus $av+b\equiv c(\mathrm{mod}m)$ Q.E.F.

Article 25

We will call any expression which takes the form of an equation, and relates two congruent quantities, a congruence; if it contains an unknown, to solve it means to find a value for this unknown which satisfies the congruence (a root). By this we understand what it means for a congruence to be solvable or unsolvable. It is easy to see that the same distinctions that apply to equations can also be applied congruences. Later we will see examples of transcendental congruences; as for algebraic congruences, they are divided according to the highest power of the unknown, into congruences of the first, second, and higher degree. One can even propose several congruences containing several unknowns, to which elimination must be applied.

Article 26

From Art. 24 it follows that first degree congruences $ax+b\equiv c$ are always solvable, provided that the modulus is relatively prime to $a.$ In this case, let $v$ be the appropriate value for $x,$ or the root of the congruence. Then it is clear that all numbers congruent to $v$ modulo $m$, will also be roots (Art. [[../First_Section#Article_9|9]]). It is equally clear that all roots must be congruent to $v:$ for if $t$ is another root, then we have $av+b\equiv at+b,$ so $av\equiv at,$ and thus $v\equiv t$ (Art. 22). We conclude from this that the congruence $x\equiv v(\mathrm{mod}m),$ gives the complete solution to the congruence $ax+b\equiv c.$

Since the congruence is solved by values of $x$ which are all congruent to each other, and in this context congruent numbers must be considered equivalent, we will consider these solutions as one and the same. Therefore, since our congruence $ax+b\equiv c,$ does not admit any other solutions, we say that it can only be solved in one way or has only one root. So e.g. the congruence $6x+5\equiv 13(\mathrm{mod}11)$ does not admit any roots other than those which are $\equiv 5(\mathrm{mod}11).$ The situation is different for higher degree congruences, and even for first degree congruences where the coefficient of the unknown is not relatively prime to the modulus.

Article 27

It remains for us to add some details about how to solve this kind of congruence. First, observe that any congruence of the form $ax+t\equiv u,$ in which the modulus is assumed to be relatively prime to $a,$ can be reduced to the congruence $ax\equiv \pm 1.$ For if $x\equiv r$ satisfies the latter, then $x\equiv \pm r(u-t)$ will satisfy the former. But the congruence $ax\equiv \pm 1$, whose modulus is denoted by $b,$ is equivalent to the indeterminate equation $ax=by\pm 1,$ whose solution is known; therefore it will be sufficient for us to provide an algorithm by which this calculation can be carried out.

If quantities $A,$ $B,$ $C,$ $D,$ $E,$ etc. depend on others $\alpha ,$ $\beta ,$ $\gamma ,$ $\delta$ etc. in such a way that

$$A=\alpha ,B=\beta A+1,C=\gamma B+A,D=\delta C+B,E=\epsilon D+C\text{ etc.}$$

then for the sake of brevity we write

$$A=[\alpha ],B=[\alpha ,\beta ],C=[\alpha ,\beta ,\gamma ],D=[\alpha ,\beta ,\gamma ,\delta ]\text{ etc.}$$

Now, consider the equation $ax=by\pm 1,$ where $a$ and $b$ are positive. Suppose, as is permitted, that $a$ is not less than $b.$ Then, according to the well-known algorithm for finding the greatest common divisor of two numbers, the following equations will be formed by division,

$$a=\alpha b+c,b=\beta c+d,c=\gamma d+e,\text{ etc.}$$

so that $\alpha ,$ $\beta ,$ $\gamma ,$ $\delta$ etc. are positive integers, and $b,$ $c,$ $d,$ $e$ etc. are continually decreasing, until we reach $m=\mu n+1;$ which must always happen. Then we will have

$$a=[n,\mu ,\dots \gamma ,\beta ,\alpha ],b=[n,\mu ,\dots \gamma ,\beta ]$$

Setting

$$x=[\mu ,\dots \gamma ,\beta ],y=[\mu ,\dots \gamma ,\beta ,\alpha ]$$

we will have $ax=by+1,$ when the number of quantities $\alpha ,$ $\beta ,$ $\gamma \dots \mu ,$ $n$ is even, and $ax=by-1,$ when it is odd.

Article 28

The general solution of these equations was first given by Euler, Comment. de Petersb. T. VII, p. 46. The method he used consists of substituting other unknowns in place of $x$ and $y,$ and it is indeed well known. Lagrange treated the problem in a slightly different manner. He observed that if one decomposes the fraction $\frac{a}{b}$ into a continued fraction

$$\frac{1}{\alpha +\frac{1}{\beta +\frac{1}{\gamma +\frac{1}{\ddots +\frac{1}{\mu +\frac{1}{n}}}}}}$$

then after erasing the last part $\frac{1}{n},$ it reduces to an ordinary fraction $\frac{x}{y},$ and one has $ax=by\pm 1,$ so long as $a$ and $b$ are relatively prime. In fact, the two methods lead to the same algorithm. Lagrange’s investigations can be found in the Histoire de l’Académie de Berlin, Année 1767, p.  175, and along with others in Supplementis versioni gallicae Algebrea Eulerianae adiectis.

Article 29

The congruence $ax+t\equiv u,$ in which the modulus is not relatively prime to $a,$ is easily reduced to the previous case. Let $m$ be the modulus and let $\delta$ be the greatest common divisor of $a$ and $m.$ It is first of all clear that any value of $x$ which satisfies the proposed congruence modulo $m,$ will also satisfy it modulo $\delta$ (Art. 5). But since $\delta$ divides $a,$ we always have $ax\equiv 0(\mathrm{mod}\delta ).$ Therefore, we must have $t\equiv u(\mathrm{mod}\delta ),$ i.e. $t-u$ must be divisible by $\delta ,$ in order for the congruence to be solvable.

Let us therefore set $a=\delta e,$ $m=\delta f,$ $t-u=\delta k,$ so that $e$ and $f$ will be relatively prime. Then the proposed congruence $\delta ex+\delta k\equiv 0(\mathrm{mod}\delta f),$ will be equivalent to $ex+k\equiv 0(\mathrm{mod}f),$ i.e. any value of $x$ that satisfies the second one will also satisfy the first one, and vice versa. For it is clear that $ex+k$ will be divisible by $f$ whenever $\delta ex+\delta k$ is divisible by $\delta f,$ and vice versa. But we have already seen how to solve the congruence $ex+k\equiv 0(\mathrm{mod}f),$ hence it is clear that if $\nu$ is one of the values of $x,$ then $x\equiv \nu (\mathrm{mod}f)$ gives the complete solution of the proposed congruence.

Article 30

When the modulus is composite, it is often advantageous to use the following method:

Let the modulus $=mn,$ and let the proposed congruence $ax\equiv b.$ First solve the congruence modulo $m,$ and suppose that it is satisfied for $x\equiv \nu (\mathrm{mod}\frac{m}{\delta }),$ where $\delta$ is the greatest common divisor of the numbers $m$ and $a.$ Now it is evident that any value of $x$ which satisfies the congruence $ax\equiv b(\mathrm{mod}mn)$ will also satisfy the congruence $ax\equiv b(\mathrm{mod}m),$ and thus it will be included in the form $\nu +\frac{m}{\delta }{x}^{\prime },$ where $x^{\prime }$ denotes an undetermined number. However, not all numbers of this form will satisfy the congruence modulo $mn.$ Rather, the values of $x^{\prime }$ must be chosen in such a way that $\nu +\frac{m}{\delta }{x}^{\prime },$ is a root of the congruence $ax\equiv b(\mathrm{mod}mn);$ hence we will have $\frac{am{x}^{\prime }}{\delta }+a\nu \equiv b(\mathrm{mod}mn)$ or equivalently $\frac{am}{\delta }{x}^{\prime }\equiv \frac{b-a\nu }{m}(\mathrm{mod}n).$ It follows from this that the solution of any congruence of the first degree modulo $mn$ can be reduced to the solution of two congruences, one modulo $m$ and the other modulo $n.$ It is easy to see that if $n$ is the product of two factors, the solution of the congruence modulo $n$ depends on the solution of two congruences with these factors as moduli; and generally, the resolution of a congruence modulo any composite modulus depends on the resolution of other congruences, whose moduli are the factors of the first one, and these moduli can always be chosen to be prime numbers, if it seems convenient.

Ex. consider the congruence $19x\equiv 1(\mathrm{mod}140);$ if we first solve it modulo $2,$ we get $x\equiv 1(\mathrm{mod}2).$ By setting $x=1+2x^{\prime },$ we get $38x^{\prime }\equiv -18(\mathrm{mod}140)$ or $19x^{\prime }\equiv -9(\mathrm{mod}70).$ Solving this modulo $2,$ we get $x^{\prime }\equiv 1(\mathrm{mod}2),$ and setting $x^{\prime }=1+2x^{″},$ we get $38x^{″}\equiv -28(\mathrm{mod}70)$ or $19x^{″}\equiv -14(\mathrm{mod}35).$ Solving this modulo $5$ gives $x^{″}\equiv 4(\mathrm{mod}5),$ and substituting $x^{″}=4+5x^{‴},$ we have $95x^{‴}\equiv -90(\mathrm{mod}35)$ or $19x^{‴}\equiv -18(\mathrm{mod}7).$ From this it follows that $x^{‴}\equiv 2(\mathrm{mod}7),$ and thus $x^{‴}=2+7x^{⁗},$ from which we have $x=59+140x^{⁗};$ therefore $x\equiv 59(\mathrm{mod}140)$ is the complete solution of the proposed congruence.

Article 31

In the same way that the root of the equation $ax=b$ is expressed by $\frac{b}{a},$ we will also denote the root of the congruence $ax\equiv b$ by $\frac{b}{a},$ including the modulus of the congruence for the sake of clarity. So e.g. $\frac{19}{17}(\mathrm{mod}12)$ represents an arbitrary number which is $\equiv 11(\mathrm{mod}12)$. It is generally clear from the above that $\frac{b}{a}(\mathrm{mod}c)$ does not have a real meaning in the case where $a$ and $c$ have a common divisor that does not divide $b$ (or, if one prefers, it is imaginary). However, except in this case, the expression $\frac{b}{a}(\mathrm{mod}c)$ will always have real values, and indeed infinitely many, which will all be congruent modulo $c$ when $a$ is relatively prime to $c$, or more generally modulo $\frac{c}{\delta }$ where $\delta$ is the greatest common divisor of $a$ and $c.$

These expressions have almost the same arithmetic as ordinary fractions. Here we add some properties that can be easily deduced from what we have already shown:

1. If $a\equiv \alpha$ and $b\equiv \beta$ modulo $c,$ then the expressions $\frac{a}{b}(\mathrm{mod}c)$ and $\frac{\alpha }{\beta }(\mathrm{mod}c)$ are equivalent.
2. $\frac{a\delta }{b\delta }(\mathrm{mod}c\delta )$ and $\frac{a}{b}(\mathrm{mod}c)$ are equivalent.
3. $\frac{ak}{bk}(\mathrm{mod}c)$ and $\frac{a}{b}(\mathrm{mod}c)$ are equivalent if $k$ is relatively prime to $c$

Many other similar propositions might be added here: but as they are not difficult, and unnecessary for what follows, we now move on to other things.

Article 32

A problem which will be of great use in what follows is to find all the numbers which form given remainders according to several given moduli. It is easy to solve this from what has already been presented. Let $A$ and $B$ be two given moduli, and let us seek a number $z$ which is congruent to the numbers $a$ and $b$ with respect to these moduli, respectively. Then all values of $z$ will necessarily be contained in the form $Ax+a,$ where $x$ is undetermined, but also satisfies $Ax+a\equiv b(\mathrm{mod}B).$ If the greatest common divisor of $A$ and $B$ is $\delta$, then the complete solution of this congruence will take the form $x\equiv v(\mathrm{mod}\frac{B}{\delta }),$ or equivalently $x=v+\frac{kB}{\delta },$ where $k$ is an undetermined integer; thus the form $a+Av+\frac{kAB}{\delta }$ contains all values of $z,$ i.e. the complete solution of the problem will be $z\equiv a+Av(\mathrm{mod}\frac{AB}{\delta }).$ Now if there were a third modulus $C,$ relative to which the number $z$ must be $\equiv c,$ then it is clear how to proceed in the same way, since the two original conditions have already been merged into one. Namely, letting $\epsilon$ be the greatest common divisor of the numbers $\frac{AB}{\delta }$ and $C,$ we will obtain the congruence $\frac{AB}{\delta }x+a+Av\equiv c(\mathrm{mod}C),$ which can be solved by a congruence of the form $x\equiv w(\mathrm{mod}\frac{C}{\epsilon }).$ Then the problem will be solved by the congruence $z\equiv \frac{AB}{\delta }w+a+Av(\mathrm{mod}\frac{ABC}{\delta \epsilon }).$ One can proceed in the same way, regardless of the number of moduli. It is worth noting that $\frac{AB}{\delta }$ and $\frac{ABC}{\delta \epsilon }$ are the least numbers divisible by $A,$ $B,$ and by $A,$ $B,$ $C,$ respectively. Thus one easily deduces, regardless of the number of moduli $A,$ $B,$ $C$ etc., that if $M$ denotes the smallest number divisible by all of them, then the complete solution will be of the form $z\equiv r(\mathrm{mod}M).$ Moreover, if one of the congruences is not solvable, it must be concluded that the problem is impossible. However, it is evident that this cannot happen if the numbers $A,B,C$ etc. are all relatively prime to each other.

Ex. Let $A=504,$ $B=35,$ $C=16,$ $a=17,$ $b=-4,$ $c=33$. Here the first two conditions, $z\equiv 17(\mathrm{mod}504)$ and $\equiv -4(\mathrm{mod}35),$ can be reduced to a single condition $z\equiv 521(\mathrm{mod}2520).$ Combining this with the third condition, $z\equiv 33(\mathrm{mod}16),$ one obtains $z\equiv 3041(\mathrm{mod}5040).$

Article 33

When the numbers $A,$ $B,$ $C$ etc. are all relatively prime to each other, their product is the smallest number divisible by each of them; and in this case it is obvious that the congruences $z\equiv a(\mathrm{mod}A),$ $z\equiv b(\mathrm{mod}B)$ etc. together will be equivalent to a single congruence $z\equiv r(\mathrm{mod}R),$ where $R$ denotes the product of the numbers $A,$ $B,$ $C$ etc. Conversely, it follows from this that a single condition $z\equiv r(\mathrm{mod}R)$ can be decomposed into several; namely, if $R$ is decomposed into several mutually relatively prime factors $A,$ $B,$ $C$ etc., then the combined conditions $z\equiv r(\mathrm{mod}A),$ $z\equiv r(\mathrm{mod}B),$ $z\equiv r(\mathrm{mod}C),$ etc. will be equivalent to the original one. This observation gives us not only the means to discover an impossibility when it exists, but also a more convenient and elegant method of calculation.

Article 34

Let the conditions proposed above be $z\equiv a(\mathrm{mod}A),$ $z\equiv b(\mathrm{mod}B),$ $z\equiv c(\mathrm{mod}C)$. Resolve all of the moduli into mutually relatively prime factors, $A$ into $A^{\prime }{A}^{″}{A}^{‴}$ etc.; $B$ into $B^{\prime }{B}^{″}{B}^{‴}$ etc. etc., so that the numbers $A^{\prime },$ $A^{″}$ etc. $B^{\prime },$ $B^{″}$ etc. etc. are either primes or powers of primes. Of course, if one of the numbers $A,$ $B,$ $C$ is already prime itself, or a power of a prime number, then it need not be resolved into factors. Then it is clear from the above that, in place of the proposed conditions, one can substitute $z\equiv a(\mathrm{mod}{A}^{\prime }),$ $z\equiv a(\mathrm{mod}{A}^{″}),$ $z\equiv a(\mathrm{mod}{A}^{‴})$ etc., $z\equiv b(\mathrm{mod}{B}^{\prime }),$ $z\equiv b(\mathrm{mod}{B}^{″})$ etc. etc. Now, unless all the numbers $A,$ $B,$ $C$ etc. are mutually prime, e.g. if $A$ and $B$ are not relatively prime, then it is clear that the prime divisors of $A$ and $B,$ cannot all be different, and one of the divisors $A^{\prime },$ $A^{″},$ $A^{‴}$ etc. must find its equal, its multiple, or its submultiple among the divisors $B^{\prime },$ $B^{″}$ $B^{‴}$ etc. In the first case, if $A^{\prime }=B^{\prime }$, then the conditions $z\equiv a(\mathrm{mod}{A}^{\prime }),$ $z\equiv b(\mathrm{mod}{B}^{\prime }),$ must be identical, or equivalently $a\equiv b(\mathrm{mod}{A}^{\prime }\text{ or }{B}^{\prime }),$ then one or the other of these two conditions can be rejected. On the other hand, if $a\equiv b(\mathrm{mod}{A}^{\prime })$ does not hold, the problem is impossible. In the second case, if $B^{\prime }$ is a multiple of $A^{\prime },$ then the condition $z\equiv a(\mathrm{mod}{A}^{\prime })$ must be contained in $z\equiv b(\mathrm{mod}{B}^{\prime }),$ or in other words it can be used to deduce $z\equiv b(\mathrm{mod}{A}^{\prime }).$ Under these conditions, the condition $z\equiv a(\mathrm{mod}{A}^{\prime })$ can be rejected, if it does not contradict the other one (in which case the problem would be impossible). When all the superfluous conditions are thus rejected, it is clear that all the remaining moduli are mutually prime; one is then sure of the possibility of the problem, and one can proceed according to the method given above.

Article 35

If as above we set $z\equiv 17(\mathrm{mod}504),$ $\equiv -4(\mathrm{mod}35),$ and $\equiv 33(\mathrm{mod}16),$ then these conditions can be reduced to the following: $z\equiv 17(\mathrm{mod}8),$ $\equiv 17(\mathrm{mod}9),$ $\equiv 17(\mathrm{mod}7);$ $z\equiv -4(\mathrm{mod}5),$ $\equiv -4(\mathrm{mod}7);$ $z\equiv 33(\mathrm{mod}16).$ From these conditions, we can reject $z\equiv 17(\mathrm{mod}8)$ and $z\equiv 17(\mathrm{mod}7),$ since the former is contained in the condition $z\equiv 33(\mathrm{mod}16),$ and the latter is equivalent to $z\equiv -4(\mathrm{mod}7);$ we are then left with

$$z\equiv \left\{\begin{array}{cc}17& (\mathrm{mod}9)\\ -4& (\mathrm{mod}5)\\ -4& (\mathrm{mod}7)\\ 33& (\mathrm{mod}16)\end{array}\right\}$$

from which we obtain

$$z\equiv 3041(\mathrm{mod}5040).$$

Now, it is clear that it would often be more convenient if, of the remaining conditions, those which had been derived from one and the same condition were combined into a single condition. This can be done easily; e.g. when some of the conditions $z\equiv a(\mathrm{mod}{A}^{\prime }),$ $z\equiv a(\mathrm{mod}{A}^{″})$ etc. have been rejected, the rest can be restored as $z\equiv a$ with respect to the modulus formed by the product of the remaining moduli. Thus in our example the condition $z\equiv -4(\mathrm{mod}35)$ can be recovered from the conditions $z\equiv -4(\mathrm{mod}5)$ and $z\equiv -4(\mathrm{mod}7).$ Now, it does make some difference which of the superfluous conditions are rejected, as far as the brevity of the calculation is concerned. But this is not the place to discuss these details or other practical tricks, which are learned from practice much more easily than from precepts.

Article 36

When the moduli $A,$ $B,$ $C,$ $D$ etc. are mutually relatively prime, it is often preferable to use the following method. Let $\alpha$ be a number which is congruent to unity modulo $A,$ and which is divisible by the product of the other moduli; that is, $\alpha$ will be any value (the minimum is generally best) of the expression $\frac{1}{BCD\text{ etc.}}(\mathrm{mod}A),$ multiplied by $BCD$ etc. (see Art. 32); similarly, let $\beta \equiv 1(\mathrm{mod}B)$ and $\equiv 0(\mathrm{mod}ACD\text{ etc.}),$ $\gamma \equiv 1(\mathrm{mod}C)$ and $\equiv 0(\mathrm{mod}ABD\text{ etc.})$ etc. Then to find a number $z$ which is congruent to the numbers $a,$ $b,$ $c,$ $d$ etc. modulo $A,$ $B,$ $C,$ $D$ etc. respectively, we can set

$$z\equiv \alpha a+\beta b+\gamma c+\text{etc.}(\mathrm{mod}ABCD\text{ etc.})$$

Then we clearly have $\alpha a\equiv a(\mathrm{mod}A),$ and the other terms are $\equiv 0(\mathrm{mod}A);$ hence $z\equiv a(\mathrm{mod}A).$ The demonstration is the same for the other moduli. This solution is preferable to the first one when solving several problems of the same kind, for which the values of $A,$ $B,$ $C$ etc. are the same; for then the values of $\alpha ,$ $\beta ,$ $\gamma$ etc. remain constant. This can be applied to the chronological problem in which we must find the Julian year which has a given indiction, the golden number, and the solar cycle. Here $A=15,$ $B=19,$ $C=28;$ thus the value of the expression $\frac{1}{19.28}(\mathrm{mod}15),$ or $\frac{1}{532}(\mathrm{mod}15),$ is $13,$ and we have $\alpha =6916.$ Similarly, we find $\beta =4200,\gamma =4845,$ hence the desired number will be the minimal residue of the number $6916a+4200b+4845c,$ where $a$ denotes the indiction, $b$ the golden number, and $c$ the solar cycle.

Article 37

Enough has been said about congruences of the first degree which contain only one unknown. It remains to deal with congruences that involve several unknowns, but since it would be too extensive to present everything rigorously in this chapter, and our goal is not to exhaust the subject here, but only to present what is most worthy of attention, we will limit our discussion to a few observations, reserving the complete exposition for another occasion.

1. Just as for equations, it can be seen that there must be as many congruences as there are unknowns for a solution to determined.

2. Let the following congruences be proposed

$$\begin{array}{ccc}ax+by+cz\dots & \equiv f\phantom{{\text{'}}^{\prime }}(\mathrm{mod}m)& ....\phantom{{\text{'}}^{\prime }}(A)\\ a^{\prime }x+b^{\prime }y+c^{\prime }z\dots & \equiv f^{\prime }\phantom{\text{'}}\phantom{(\mathrm{mod}m)}& ....\phantom{\text{'}}(A^{\prime })\\ a^{″}x+b^{″}y+c^{″}z\dots & \equiv f^{″}\phantom{(\mathrm{mod}m)}& ....(A^{″})\end{array}$$

and assume that the number of these congruences is the same as the number of unknowns $x,$ $y,$ $z$ etc.

Then determine numbers $\xi ,$ ${\xi }^{\prime },$ ${\xi }^{″}$ etc. so that

$$\begin{array}{cc}b\xi +b^{\prime }{\xi }^{\prime }+b^{\prime }{\xi }^{″}+\text{etc.}& =0,\\ c\xi +c^{\prime }{\xi }^{\prime }+c^{″}{\xi }^{″}+\text{etc.}& =0,\\ \text{ etc.}\end{array}$$

and so that these numbers are integers with no common divisor (which is always possible, by the theory of linear equations).

In a similar way, determine $\nu ,$ ${\nu }^{\prime },$ ${\nu }^{″}$ etc., $\zeta ,$ ${\zeta }^{\prime },$ ${\zeta }^{″}$ etc. etc. so that

$$\begin{array}{cc}a\nu +a^{\prime }{\nu }^{\prime }+a^{″}{\nu }^{″}+\text{etc.}& =0\\ c\nu +c^{\prime }{\nu }^{\prime }+c^{″}{\nu }^{″}+\text{etc.}& =0\\ \text{etc.}& \\ a\zeta +a^{\prime }{\zeta }^{\prime }+a^{″}{\zeta }^{″}+\text{etc.}& =0\\ b\zeta +b^{\prime }{\zeta }^{\prime }+b^{″}{\zeta }^{″}+\text{etc.}& =0,\\ \text{etc.}& \end{array}$$

3. It is clear that if we multiply the congruences $A,$ $A^{\prime },$ $A^{″}$ etc. first by $\xi ,$ ${\xi }^{\prime },$ ${\xi }^{″}$ etc. and then by $\nu ,$ ${\nu }^{\prime },$ ${\nu }^{″}$ etc. etc. and add them, we will obtain the following:

$$\begin{array}{cc}(a\xi +a^{\prime }{\xi }^{\prime }+a^{″}{\xi }^{″}+\text{etc.})x& \equiv f\xi +f^{\prime }{\xi }^{\prime }+f^{″}{\xi }^{″}+\text{etc.}\\ (b\nu +b^{\prime }{\nu }^{\prime }+b^{″}{\nu }^{\prime }+\text{etc.})y& \equiv f\nu +f^{\prime }{\nu }^{\prime }+f^{″}{\nu }^{″}+\text{etc.}\\ (c\zeta +c^{\prime }{\zeta }^{\prime }+b^{″}{\zeta }^{″}+\text{etc.})z& \equiv f\zeta +f^{\prime }{\zeta }^{\prime }+f^{″}{\zeta }^{″}+\text{etc.}\end{array}$$

For the sake of brevity, we will write these congruences as

$$\mathrm{\Sigma }(a\xi )x\equiv \mathrm{\Sigma }(f\xi ),\mathrm{\Sigma }(b\nu )y\equiv \mathrm{\Sigma }(f\nu ),\mathrm{\Sigma }(c\zeta )z\equiv \mathrm{\Sigma }(f\zeta )\text{etc.}$$

4. There are now several cases to distinguish.

First, when the coefficients of the unknowns, $\mathrm{\Sigma }(a\xi ),$ $\mathrm{\Sigma }(b\nu )$ etc. are all relatively prime to the modulus $m$, the above congruences can be solved by the methods already presented, and the complete solution of the problem will be given by congruences of the form $x\equiv p(\mathrm{mod}m),$ $y\equiv q(\mathrm{mod}m)$ etc.. E.g. if we propose the congruences

$$x+3y+z\equiv 1,4x+y+5z\equiv 7,2x+2y+z\equiv 3(\mathrm{mod}8),$$

we will find $\xi =9,$ ${\xi }^{\prime }=1,$ ${\xi }^{″}=-14,$ hence $-15x\equiv -26$ and therefore $x\equiv 6(\mathrm{mod}8);$ likewise, we will find $15y\equiv -4,$ $15z\equiv 1,$ and hence $y\equiv 4,$ $z\equiv 7(\mathrm{mod}8).$

5. Second, If the coefficients $\mathrm{\Sigma }(a\xi ),$ $\mathrm{\Sigma }(a\xi ),$ $\mathrm{\Sigma }(b\nu )$ etc. are not all relatively prime to the modulus, let $\alpha ,$ $\beta ,$ $\gamma$ etc. be the greatest common divisors of $m$ and $\mathrm{\Sigma }(a\xi ),$ $\mathrm{\Sigma }(b\nu ),$ $\mathrm{\Sigma }(c\zeta )$ etc. respectively. Then it is clear that the problem is impossible unless the numbers $\mathrm{\Sigma }(f\xi ),$ $\mathrm{\Sigma }(f\nu ),$ $\mathrm{\Sigma }(f\zeta )$ etc. are divisible by $\alpha ,$ $\beta ,$ $\gamma$ etc. respectively. On the other hand, when these conditions hold, the problem will be completely solved by congruences of the form $x\equiv p(\mathrm{mod}\frac{m}{\alpha }),y\equiv q(\mathrm{mod}\frac{m}{\beta }),z\equiv r(\mathrm{mod}\frac{m}{\gamma })$ etc., or if you prefer, there will be $\alpha$ different values for $x$ (i.e. the values $p,p+\frac{m}{\alpha },\dots p+\frac{(\alpha -1)m}{\alpha },$ which are incongruent modulo $m$), $\beta$ values for $y,$ etc. that will satisfy the congruences. Clearly, all solutions to the problem, if there are any, must be found among those we have just indicated. However, it is not allowed to reverse this conclusion; for in general it is not true that all combinations of the $\alpha$ values of $x,$ with those of $y$ and those of $z$ etc. will satisfy the problem, but only some of them whose connection must be expressed by means of one or more conditional congruences. However, since the complete solution of this problem is not necessary for the following, we will not go any further on this subject and content ourselves to give the idea with an example.

Let the following congruences be proposed:

$$3x+5y+z\equiv 4,2x+3y+2z\equiv 7,5x+y+3z\equiv 6(\mathrm{mod}12),$$

Then we will have

$$\begin{array}{cccccc}\xi & =1,& {\xi }^{\prime }& =-2,& {\xi }^{″}& =1,\\ \nu & =1,& {\nu }^{\prime }& =1,& {\nu }^{″}& =-1,\\ \zeta & =-13,& {\zeta }^{\prime }& =22,& {\zeta }^{″}& =-1,\end{array}$$

hence $4x\equiv -4,$ $7y\equiv 5,$ $28z\equiv 96.$ From this we obtain four values of $x,$ namely, $x\equiv 2,$ $5,$ $8,$ $11;$ one value of $y,$ namely $y\equiv 11;$ and four values of $z,$ namely, $z\equiv 0,3,6,9(\mathrm{mod}12).$ To find out which combinations of the values of $x$ and $z$ are permissible, substitute $2+3t,$ $11,$ $3u,$ for $x,$ $y,$ $z$ in the given congruences. After this, they become

$$57+9t+3u\equiv 0,30+6t+6u\equiv 0,15+15t+9u\equiv 0(\mathrm{mod}12),$$

which are easily seen to be equivalent to

$$19t+3t+u\equiv 0,10+2t+2u\equiv 0,5+5t+3u\equiv 0(\mathrm{mod}4).$$

The first congruence clearly requires that $u\equiv t+1(\mathrm{mod}4),$ and the rest will clearly be satisfies if this value is substituted in them. We conclude from this that the values $x\equiv 2,$ $5,$ $8,$ $11$ (which are obtained by successively setting $t=0,$ $1,$ $2,$ $3$) must be combined respectively with the values $z\equiv 3,$ $6,$ $9,$ $0,$ so there are four solutions altogether,

$$\begin{array}{cccccc}x\equiv & 2,& 5,& 8,& 11& (\mathrm{mod}12)\\ y\equiv & 11,& 11,& 11,& 11\\ z\equiv & 3,& 6,& 9,& 0\end{array}$$

To these investigations, which complete the task we had set ourselves in this section, we will add some propositions based on similar principles, which will be needed frequently in what follows.

Article 38

Template:Sc Determine how many numbers are less than and relatively prime to a given positive number $A.$

For the sake of brevity, let us denote the number we seek by the prefixed symbol $\varphi$. So, the problem is to find $\varphi A.$

I. When $A$ is prime, it is clear that all numbers from $1$ to $A-1,$ are relatively prime to $A;$ therefore, in this case, we have

$$\varphi A=A-1.$$

II. When $A$ is a power of a prime number $p,$ say $p^m,$ then all numbers divisible by $p$ will not be prime with $A,$ and the others will be. Therefore, of the $p^m-1$ numbers, we must reject $p,$ $2p,$ $3p$ $\dots$ $(p^{m-1}-1)p;$ so there remain $p^m-1-(p^{m-1}-1).$ Hence

$$\varphi p^m=p^{m-1}.(p-1).$$

III. The other cases can be easily reduced to these, by means of the following proposition: If we factor $A$ into factors $M,$ $N,$ $P\dots$ etc. which are all relatively prime to each other, then

$$\varphi A=\varphi M.\varphi N.\varphi P\text{ etc.}$$

which can demonstrated as follows. Let $m,$ $m^{\prime },$ $m^{″}$ etc. be the numbers which are less than and relatively prime to $M$, whose multitude is therefore $\varphi M$. Similarly, let the numbers less than and relatively prime to $N,$ $P$ etc. be $n,$ $n^{\prime },$ $n^{″}$ etc.; $p,$ $p^{\prime },$ $p^{″}$ etc. etc., whose multitudes are $\varphi P,$ $\varphi N$ etc. It is clear that any number relatively prime to $A$ will also be relatively prime to the factors $M,$ $N,$ $P$ etc. and vice versa (Art. 19). Furthermore, all numbers that are congruent to one of the numbers $m,$ $m^{\prime },$ $m^{″}$ etc. modulo $M$ will be relatively prime to $M,$ and the same applies for $N,$ $P$ etc. The question is therefore reduced to determining how many numbers are less than $A$ and congruent to one of the numbers $m,$ $m^{\prime },$ $m^{″}$ etc. modulo $M,$ to one of the numbers $n,$ $n^{\prime },$ $n^{″}$ etc. modulo $N$, etc. However, it follows from Art. 32 that all numbers with given residues modulo $M,$ $N,$ $P$ etc. must be congruent modulo the product $A,$ and therefore there can only be one number less than $A$ which is congruent to the given residues modulo $M,$ $N,$ $P$ etc. Therefore, the number we seek will be equal to the number of combinations of the individual numbers $m,$ $m^{\prime },$ $m^{″}$ etc. with the individual numbers $n,$ $n^{\prime },$ $n^{″}$ etc. and $p,$ $p^{\prime },$ $p^{″}$ etc. etc. It is evident from the theory of combinations that this number is $\varphi (M).\varphi (N).\varphi (P)$ etc. Q.E.D.

IV. It is easy to see how to apply this proposition in the case at hand. We will decompose $A$ into prime factors; that is, we will reduce it to the form $a^{\alpha }{b}^{\beta }{c}^{\gamma }$ etc., with $a,$ $b,$ $c$ etc. being distinct prime numbers. Then we will have

$$\varphi A=\varphi a^{\alpha }\varphi b^{\beta }\varphi c^{\gamma }\text{ etc.}=a^{\alpha -1}(a-1)\cdot b^{\beta -1}(b-1)\cdot c^{\gamma -1}(c-1)\text{ etc.}$$

which can be put in the more elegant form

$$\varphi A=A\cdot \frac{a-1}{a}\cdot \frac{b-1}{b}\cdot \frac{c-1}{c}\text{ etc.}$$

Example: Take $A=60=2^2\cdot 3\cdot 5.$ Then we have $\varphi A=60\cdot \frac{1}{2}\cdot \frac{2}{3}\cdot \frac{4}{5}=16.$ The numbers which are less than and relatively prime to $60$ are $1,$ $7,$ $11,$ $13,$ $17,$ $19,$ $23,$ $29,$ $31,$ $37,$ $41,$ $43,$ $47,$ $49,$ $53,$ $59.$

The first solution of this problem can be found in Euler’s commentary, Theoremata arithmetica nova methodo demonstrata, Comm. nov. Ac. Petrop. VIII p. 74. A demonstration was also provided in another dissertation Speculationes circa quasdam insignes proprietates numerorum Acta Petrop. VIII, p. 17.

Article 39

If the meaning of the symbol $\varphi$ is determined in such a way that $\varphi A$ expresses how many numbers are relatively prime to $A$ and not greater than $A,$ then we will have $\varphi 1=1$ instead of $0.$ However, in all other cases, nothing will change. Adopting this definition, we have the following theorem:

If $a,$ $a^{\prime },$ $a^{″}$ etc. are all of the divisors of $A,$ including 1 and $A,$ then

$$\varphi a+\varphi a^{\prime }+\varphi a^{″}+\text{etc.}=A.$$

Ex. If $A=30,$ we have

$$\varphi 1+\varphi 2+\varphi 3+\varphi 5+\varphi 6+\varphi 10+\varphi 15+\varphi 30=1+1+2+4+2+4+8+8=30$$

Proof. If we multiply all numbers coprime with $a$ and not greater than $a$ by $\frac{A}{a},$ and similarly all numbers coprime with $a^{\prime }$ by $\frac{A}{a^{\prime }}$ etc., then we will have $\varphi a+\varphi a^{\prime }+\varphi a^{″}+$ etc. numbers, all of which are not greater than $A.$ However,

1. All of these numbers will be distinct. Indeed, it is clear that those coming from the same divisor of $A$ are all distinct. On the other hand, if two equal numbers resulted from different divisors $M$ and $N,$ and from numbers $\mu$ and $\nu$ respectively, that is, if $\frac{A}{M}\mu =\frac{A}{N}\nu ,$ then we would have $N\mu =M\nu .$ Assuming that $M>N$ (which is allowed), then since $M$ is relatively prime to $\mu$ and divides $N\mu ,$ it would follow that the larger number $M$ divides the smaller number $N,$ Q.E.A.
2. Among these numbers, we will find all of those which make up the sequence $1,2,3,\dots ,A.$ Indeed, let $t$ be any number that does not exceed $A,$ and let $\delta$ be the greatest common divisor of $A$ and $t.$ Then $\frac{A}{\delta }$ will be a divisor of $A$ which is relatively prime to $\frac{t}{\delta }$. Then clearly the number $t$ will be among those that were produced by the divisor $\frac{A}{\delta }$.
3. It follows from this that the multitude of these numbers is $A,$ and hence

Article 40

If $\mu$ is the greatest common divisor of the numbers $A,$ $B,$ $C,$ $D$ etc., then numbers $a,$ $b,$ $c,$ $d$ etc. can be determined so that

$$aA+bB+cC+\text{etc.}=\mu .$$

Let us first consider only two numbers $A$ and $B,$ and let $\lambda$ be their greatest common divisor. Then the congruence $Ax\equiv \lambda (\mathrm{mod}B)$ will be solvable (Art. 30). Let the root be $\equiv \alpha ,$ and set $\frac{\lambda -A\alpha }{B}=\beta .$ Then we will have $\alpha A+\beta B=\lambda ,$ as desired.

If there is a third number $C,$ let ${\lambda }^{\prime }$ be the greatest common divisor of $\lambda$ and $C.$ Note that ${\lambda }^{\prime }$ will also be the greatest common divisor of the three numbers $A,$ $B,$ $C$. Then let numbers $k$ and $\gamma$ be determined so that $k\lambda +\gamma C={\lambda }^{\prime },$ and we will have $k\alpha A\lambda +k\beta B+\gamma C={\lambda }^{\prime }.$

If there is a fourth number $D,$ let ${\lambda }^{″}$ be the greatest common divisor of ${\lambda }^{\prime }$ and $D$ (which, it is easily seen, will also be the greatest common divisor of the four numbers $A,$ $B,$ $C,$ and $D$). Then let $k^{\prime }{\lambda }^{\prime }+\delta D={\lambda }^{″},$ and we will have $k^{\prime }k\alpha A+k^{\prime }k\beta B+k^{\prime }\gamma C+\delta D={\lambda }^{″}.$

We would proceed in a similar way if there were more numbers.

In particular, if the numbers $A,$ $B,$ $C$ etc. have no common divisor, then it is clear that we can find $A,$ $B,$ $C$ etc. so that

$$aA+bB+cC+\text{etc.}=1.$$

Article 41

If $p$ is a prime number, and if there are $p$ objects among which any number may be equal (provided that they are not all equal), then the number of permutations of these objects will be divisible by $p.$

For example, five objects $A,A,A,B,B$ can be arranged in ten different ways.

The demonstration of this theorem is easily deduced from the well-known theory of permutations. Indeed, suppose that, among these $p$ things, there are $a$ equal to $A,$ $b$ equal to $B,$ $c$ equal to $C$ etc. (where the numbers $a,$ $b,$ $c\dots$ can also represent unity), so that we have

$$a+b+c+\dots =p$$

Then the number of permutations will be

$$=\frac{1.2.3\dots \dots p}{1.2\dots a.1.2\dots b.1.2\dots c\text{ etc.}}$$

It is clear that the numerator of this fraction is divisible by the denominator, since the number of permutations is an integer: but the numerator is divisible by $p,$ whereas the denominator, which is composed of factors smaller than $p,$ is not divisible by $p$ (Art. 15). Therefore, the number of permutations will be divisible by $p$ (Art. 19).

That being said, we hope that the following demonstration will not be unwelcome.

When in two permutations the order of the objects only differs in that the item which occupied the first place in one, now occupies a different one in the other, while the other objects, starting from that one, follow the same order in each of the permutations, so that the last item in one is immediately before the first item in the other. Then we will call them similar permutations. So, for example, the permutations $ABAAB$ and $ABABA$ will be similar, since the things which in the former occupy the first place, second place, etc. occupy the third place, fourth place, etc. in the latter.

Now, as each permutation consists of $p$ objects, it is clear that one can find $p-1$ similar permutations, if one puts successively at the second place, third place, etc. the item which occupied the first place. Therefore, if none of these similar permutations are identical, it is evident that the total number of permutations will be equal to $p$ times the number of dissimilar permutations, and consequently will be divisible by $p.$ Let us suppose, then, that two similar permutations

$$PQ\dots TV\dots YZ,V\dots YZPQ\dots T$$

one of which has arisen from the other by the promotion of terms, are identical, in the sense that $P=V$ etc. Suppose that the term $P,$ which occupies the first place in the first permutation, occupies the ${n+1}^{st}$ in the second. Then in the latter series, the ${n+1}^{st}$ term will be equal to the first, the ${n+2}^{nd}$ will be equal to the second, etc., from which it follows that the ${2n+1}^{st}$ will again be equal to the first, and likewise for the ${3n+1}^{st},$ and in general the ${kn+m}^{th}$ will be equal to the $m^{th}$ (where, when $kn+m>p,$ it is necessary to imagine that either the series $V\dots YZPQ\dots T$ is repeated from the beginning, or that we subtract a multiple of $p$ from $kn+m$). Therefore, if we determine $k$ in such a way that $kn\equiv 1(\mathrm{mod}p),$ which can always be done since $p$ is prime, it will follow that generally the $m^{th}$ term will be equal to the ${m+1}^{st},$ i.e. all the terms will be equal to each other, contrary to the hypothesis.

Article 42

If the coefficients $A,$ $B,$ $C\dots N;$ $a,$ $b,$ $c\dots n;$ of two functions of the form

$$\begin{array}{cc}{x}^m+A{x}^{m-1}+B{x}^{m-2}+C{x}^{m-3}\dots +N& ....(P)\\ x^{\mu }+a{x}^{\mu -1}+b{x}^{\mu -2}+c{x}^{\mu -3}\dots +n& ....(Q)\end{array}$$

are all rational, but not all integers, and their product is

$$x^{m+\mu }+𝔄x^{m+\mu -1}+𝔅x^{m+\mu -2}\dots +𝔑,$$

then the coefficients $𝔄,$ $𝔅\dots 𝔑$ cannot all be integers.

Indeed, let us simplify to their simplest form all fractions that may be found among the numbers $A,$ $B$ etc. $a,$ $b$ etc., and choose a prime number $p$ that divides one or more of the denominators of these fractions. Let us assume, as we may, that $p$ divides the denominator of a fractional coefficient in $(P).$ It is clear that if $(Q)$ is divided by $p,$ then at least one fractional coefficient in $\frac{(Q)}{p}$ will have a denominator divisible by $p$ (in particular, the coefficient of the first term will be $\frac{1}{p}$). It is then easy to see that in $(P)$ there is a term whose denominator contains a power of $p$ raised to a power which is greater than in all of the preceding terms, and not less than in all of the terms which follow. Let $G{x}^g$ be such a term, and let $t$ be the exponent of $p$ in its denominator. Let the analogous term in $\frac{(Q)}{p}$ be $\mathrm{\Gamma }{x}^{\gamma },$ and let the exponent of $p$ in the denominator be $\tau .$ Then clearly $t+\tau$ will be at least $2.$ With this in mind, the term $x^{g+\gamma }$ of the product of $(P)$ and $(Q)$ will have a fractional coefficient whose denominator contains $p$ raised to the power $t+\tau -1,$ as will now be shown.

Let $\text{'}G{x}^{g+1},$ ${\text{'}}^{\prime }G{x}^{g+2}$ etc. be the terms preceding $G{x}^g$ in $(P),$ and let $G^{\prime }{x}^{g-1},$ $G^{″}{x}^{g-2}$ etc. be those which follow it. Similarly, let $\text{'}\mathrm{\Gamma }{x}^{\gamma +1},$ ${\text{'}}^{\prime }\mathrm{\Gamma }{x}^{\gamma +2}$ etc. be the terms preceding $\mathrm{\Gamma }{x}^{\gamma }$ in $\frac{(Q)}{p},$ and let ${\mathrm{\Gamma }}^{\prime }{x}^{\gamma -1},$ ${\mathrm{\Gamma }}^{″}{x}^{\gamma -2}$ be those which follow it. Then in the product of $(P)$ and $\frac{(Q)}{p},$ the coefficient of $x^{g+\gamma }$ will clearly be

$$\begin{array}{cc}=G\mathrm{\Gamma }& +\text{'}G{\mathrm{\Gamma }}^{\prime }+{\text{'}}^{\prime }G{\mathrm{\Gamma }}^{″}+\dots .\\ & +\text{'}\mathrm{\Gamma }{G}^{\prime }+{\text{'}}^{\prime }\mathrm{\Gamma }{G}^{″}+\dots .\end{array}$$

The term $G\mathrm{\Gamma }$ will be a fraction which, when reduced to its simplest form, will have a denominator divisible by $p^{t+\tau }.$ If the other terms are fractional, then their denominators will contain only powers of $p$ less than $p^{t+\tau },$ since each of them is the product of two factors, one of which contains only a power of $p$ smaller than $p^t$ or $p^{\tau },$ and the other a power not greater than $p^t$ or $p^{\tau }.$ Thus $G\mathrm{\Gamma }$ will be of the form $\frac{e}{f{p}^{t+\tau }},$ and the rest will be of the form $\frac{e^{\prime }}{f^{\prime }{p}^{t+\tau -\delta }},$ where $e,$ $f,$ and $f^{\prime }$ are relatively prime to $p.$ Therefore the sum of these will be $=\frac{e{f}^{\prime }+e^{\prime }f{p}^{\delta }}{f{f}^{\prime }{p}^{t+\tau }},$ a fraction whose numerator is not divisible by $p.$ Hence this fraction cannot be reduced in any way so that its denominator contains a a power of $p$ smaller than $p^{t+\tau }.$ Therefore, the coefficient of the term $x^{g+\gamma }$ in the product of $(P)$ by $(Q)$ will be

$$\frac{e{f}^{\prime }+e^{\prime }f{p}^{\delta }}{f{f}^{\prime }{p}^{t+\tau -1}}$$

i.e. a fraction, whose denominator is divisible by at least the ${t+\tau -1}^{st}$ power of $p.$ Q.E.D.

Article 43

A congruence of the $m^{th}$ degree,

$$A{x}^m+B{x}^{m-1}+C{x}^{m-2}+\dots +Mx+N\equiv 0$$

whose modulus is a prime number $p$ that does not divide $A,$ cannot have more than $m$ solutions, or equivalently cannot have more than $m$ incongruent roots modulo $p$ (See Arts. 25, 26).

If anyone denies it, let us suppose that congruences of different degrees $m,$ $n$ etc. are given, which have more than $m,$ $n$ etc. roots. Let $m$ be the smallest of all of these, so that all congruences of degree lower than $m$ are consistent with our theorem. Since it has already been demonstrated above (Art. 26) that the theorem holds for congruences of the first degree, it is clear that $m$ will be $=2$ or greater. Let us therefore assume that the congruence

$$A{x}^m+B{x}^{m-1}+C{x}^{m-2}+\dots +Mx+N\equiv 0$$

has at least $m+1$ roots $x\equiv \alpha ,$ $x\equiv \beta ,$ $x\equiv \gamma$ etc., and suppose that all of the numbers $\alpha ,$ $\beta ,$ $\gamma$ etc. are positive and less than $p,$, with the smallest being $\alpha$. Now let us substitute $y+\alpha$ for $x$ in the proposed congruence, with the result being

$$A^{\prime }{y}^m+B^{\prime }{y}^{m-1}+\dots +M^{\prime }y+N^{\prime }\equiv 0$$

Then it is clear that this congruence will be satisfied if we put $y\equiv 0$ or $\equiv \beta -\alpha ,$ or $\equiv \gamma -\alpha$ etc., and that all of these roots will be distinct, with their multitude being $m+1.$ However, since $y\equiv 0$ is a root, it follows that $N^{\prime }$ is divisible by $p.$ From this we obtain

$$y(A^{\prime }{y}^{m-1}+B^{\prime }{y}^{m-2}+\dots +M^{\prime })\equiv 0(\mathrm{mod}p)$$

a congruence that will be satisfied by substituting for $y$ any of the $m$ values $\beta -\alpha ,$ $\gamma -\alpha$ etc. which are all $>0$ and $<p,$ and therefore in these cases

$$A{y}^{m-1}+B^{\prime }{y}^{m-2}+\dots +M^{\prime }$$

will become $\equiv 0$ (Art. 22), i.e. the congruence

$$A{y}^{m-1}+B^{\prime }{y}^{m-2}+\dots +M^{\prime }\equiv 0,$$

which is of degree $m-1,$ would have $m$ roots; which contradicts our theorem (for it is easy to see that $A;=A,$ and therefore it is not divisible by $p,$ as required), even though we assumed that all congruences of a degree lower than $m$ satisfy it. Q.E.A.

Article 44

Although we have assumed here that the modulus $p$ does not divide the coefficient of the first term, the theorem is not restricted to this case. For if the first coefficient, and even some of the following ones, were divisible by $p,$ then these terms could be neglected without error, and the congruence would be reduced to a lower degree, such that the coefficient of the first term would no longer be divisible by $p.$ Indeed, not all coefficients can be divisible by $p$; in this case the congruence would be an identity, and the unknown would be completely indeterminate.

Lagrange was the first to propose and prove the theorem (Mem. de l'Ac de Berlin, Année 1768 p.192). It is also found in Legendre’s dissertation, Recherches d’Analyse indéterminée, Hist. de l'Acad. de Paris 1785 p. 466). Euler proved, in Nouveaux Commentaires Académiques. Pétersb. XVIII, p. 93, that the congruence $x^n-1\equiv 0$ could not have more than $n$ roots. Although this is only a particular case, his method can easily be applied to all congruences. He had already dealt with a still more limited case, Comm. nov. Ac. Petr. V. p. 6, but this method cannot be used in general. In Section VIII below, we will demonstrate this theorem in yet another way; but no matter how different all these methods may seem at first glance, experts who wish to compare them will easily verify that they all originate from the same principle. Furthermore, this theorem should only be considered here as a lemma, and the complete exposition does not belong to this section, so we will treat the case of a composite modulus elsewhere.