Read an Excerpt
CHAPTER 1
Equations in One Unknown
Let us consider equations of the first degree in one unknown
a1x + a0 = 0. (1)
Let the coefficients a1 and a0 in the equation be integers. It is clear that the solution of this equation,
x = a0/a1,
will be an integer only if a1 integrally divides a0. Thus equation (1) is not always solvable in integers. For example, of the two equations 3x - 27 = 0 and 5x + 21 = 0, the first has the integer solution x = 9, but the second is unsolvable in integers.
The same situation is met in equations of degree higher than the first. The quadratic equation x2 + x - 2 = 0 has integer solutions x1 = 1, x2 = -2; but the equation x2 - 4x + 2 = 0 is unsolvable in integers since its roots x1,2 = 2 [+ or -] [square root of 2] are irrational.
The problem of finding integral roots of equations of the nth degree with integral coefficients
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2)
is easily solved. Indeed, let x = a be an integral root of this equation. Then
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
From the last equation it is seen that a0 is divisible by a without remainder. Consequently, every integer root of equation (2) is a divisor of the constant term of the equation. In order to find the integral solutions of the equation, it is necessary to choose those of the divisors of a0 which, when substituted into the equation, convert it into an identity. Thus, for example, of the numbers 1, -1, 2, -2 representing all divisors of the constant term of the equation
x10 + x7 + 2x3 + 2 = 0,
only -1 is a root. Consequently this equation has a unique integral root x = -1. In the same way, it is easy to show that the equation
x6 - x5 + 3x4 + x2 - x + 3 = 0
has no integral solutions.
Of considerably greater interest is the solution in integers of equations with many unknowns.
2. Equations of the First Degree in Two Unknowns
Let us consider equations of the first degree with two unknowns
ax + by + c = 0, (3)
where a and b are integers different from 0 and c is an arbitrary integer. We will consider the case that the coefficients a and b do not have a common divisor other than unity. Indeed, if the greatest common divisor d = (a, b) is distinct from unity, then a = a1d, b = b1d, and equation (3) takes the form
(a1x + b1y)d + c = 0.
This equation has an integral solution only when c is divisible by d. Thus, in the case (a, b) = d ≠ 1, all coefficients of the equation (3) are necessarily divisible by d, and the canceling of d leads to the equation
a1x + b1y + c1 = 0 (c1 = c/d),
in which the coefficients a1 and b1 are relatively prime.
We consider first the case when c - 0. Equation (3) is then
ax + by - 0. (3')
Solving this equation for x yields
x = -(b/a)y.
It is clear that x will take integral values when and only when a divides y without remainder. But every y which is a multiple of a may be written in the form
y = at,
where t takes on arbitrary integral values (t = 0, [+ or -]1, [+ or -]2, ...). If we substitute these values of y in the preceding equation, then
x = -(b/a)at = -bt,
and we obtain formulas containing all integral solutions of the equation (3'):
x = -bt, y - at (t = 0, [+ or -]1, [+ or -]2, ...).
We proceed now to the case c ≠ 0.
We show first that in order to find all solutions of equation (3) it is sufficient to find any one of its solutions, that is, to find integers x0, y0 for which
ax0 by0 + c = 0.
THEOREM I. Let a and b be relatively prime and let [x0, y0] be any solution of the equation
ax + by + c = 0. (3)
Then the formulas
x = x0 - bt, y = y0 + at (4)
for t = 0, [+ or -]1, [+ or -]2, ..., give all solutions of equation (3).
Proof: Let [x, y] be an arbitrary solution of equation (3). Then from the equalities
ax + by + c = 0 and ax0 + by0 + c = 0
we obtain
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
Since y - y0 is an integer and a and b are relatively prime, it is necessary that b divide x0 - x; that is, x0 - x has the form
x0 - x = bt,
where t is an integer. But then
y - y0 = abt/b = at,
and we obtain
x = x0 - bt, y = y0 + at.
Thus it is proved that every solution [x, y] has the form (4). It still remains to be verified that every pair of numbers [x, y] obtained from (4) for integral t = t1 will be a solution of (3). In order to draw this inference, we substitute the quantities x1 = x0 - bt1, y1 = y0 + at1 into the left side of equation (3):
ax1 + by1 + c = ax0 - abt1 + by0 + abt1 + c = ax0 + by0 + c.
But since [x0, y0] is a solution, ax0 + by0 + c = 0 and, consequently,
ax1 + by1 + c = 0;
that is, [x1, y1] is a solution of (3) and the theorem is completely proved.
Thus, if one solution of the equation ax + by + c = 0 is known, then all the remaining solutions are found from the arithmetic progression, the general term of which has the form
x = x0 - bt, y = y0 + at (t = 0, [+ or -]1, [+ or -]2, ...).
We note that in the case c = 0, the solutions
x = -bt, y = at
found earlier may be obtained from the formulas
x = x0 - bt, y = y0 + at
if we choose x0 = y0 = 0. It is possible to make this choice since the pair x = 0, y = 0 is evidently a solution of the equation ax + by = 0.
How is a solution [x0, y0] of equation (3) found in the general case when c ≠ 0? Let us begin with an example — with the equation
127x - 52y + 1 = 0.
We shall transform the ratio of the coefficients of the unknowns.
First, we separate out the integral part of the improper fraction 127/52:
127/52 = 2 + 23/52.
The proper fraction 23/52 we replace by the equal fraction 1/(52/23).
Then we obtain
127/52 = 2 + 1/(52/23).
We perform the same transformation on the improper fraction 52/23 obtained in the denominator:
52/23 = 2 + 6/23 = 2 + 1/(23/6).
Now the original fraction takes the form
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
We repeat the same argument for the fraction 23/6:
23/6 = 3 + 5/6 = 3 + 1/(6/5).
Then
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
Separating out the integral part of the fraction 6/5,
6/5 = 1 + 1/5,
leads to the final result
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
We have obtained an expression which is called a finite continued fraction. We remove the last term, 1/5, of this continued fraction, convert the resulting continued fraction into a simple fraction, and subtract from the original fraction 127/52:
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
If we bring the resulting equation to a common denominator and then reject the denominator, we obtain
127 x 9 - 52 x 22 + 1 = 0.
From a comparison of this equality with the equation
127x - 52y + 1 = 0
it follows that x = 9, y = 22 is a solution of the equation, and according to the theorem all of its solutions will be contained in the progression
x = 9 + 52t, y = 22 + 127t (t = 0, [+ or -]1, [+ or -]2, ...).
The result leads to the thought that in the general case in order to find a solution of the equation ax + by + c = 0 it is sufficient to decompose the quotient of the coefficients of the unknowns into a continued fraction, reject its last term, and perform a calculation similar to that which was carried out above.
For a proof of this supposition, we shall need certain properties of continued fractions.
We consider the irreducible fraction a/b. We designate the integral part by q1 and the remainder by r2 when we divide a by b. We obtain
a = q1b + r2, r2< b.
Let, further, q2 and r3 be the integral part and remainder respectively when we divide b by r2. Then
b = q2r2 + r3, r3< r2,
and in the same way
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
The quantities q1, q2, ..., are called the partial quotients. The above process for the formation of the partial quotients is called the Euclidean algorithm. The remainders r2, r3, ..., satisfy the inequalities
b > r2 > r3 > r4 > ... ≥ 0, (5)
that is, they form a decreasing sequence of non-negative integers. Since the number of non-negative integers not exceeding b is finite, the above process must stop at a certain place because of the vanishing of the remainder r. Let rn be the last non-zero remainder in the sequence (5). Then rn+1 = 0 and the Euclidean algorithm for the numbers a and b takes the form
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)
We transcribe these equations into the form
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
Replacing the value b/r2 in the first line by its equal from the second line, the value r2/r3 by its equal from the third line, and so forth, we obtain an expansion of a/b in a continued fraction
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
The expression obtained from a continued fraction by rejecting all of its terms beginning with a certain term we call a convergent. We obtain the first convergent 81 by rejecting all terms beginning with 1/q2:
δ1 = q1< a/b.
The second convergent 82 is obtained by rejecting all terms beginning with 1/q2:
b2 = q1 + 1/q2 > a/b.
In the same way,
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
and so forth.
As a consequence of the method of formation of the convergents, we evidently have the inequalities
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
We write the kth convergent δk in the form
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
and seek the law of formation of the numerator and denominator of this convergent. We transform first the convergents δ1, δ2, and δ3:
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
From this we obtain
P3 = P2q3 + P1; Q3 = Q2q3 + Q1.
We shall show by induction that the corresponding forms
Pk = Pk-1qk + Pk-2, Qk = Qk-1qk + Qk-2 (7)
are satisfied for all k ≥ 3.
Indeed, let the equalities (7) be satisfied for a certain k ≥ 3. From the definition of a convergent, it follows immediately that if we replace in δk the number qk by qk + 1/qk+1, then δk is transformed into δk+1. According to the induction hypothesis,
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
Replacing qk by qk + 1/qk+1 we obtain
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
Hence, since
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
it follows that
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
Thus from the truth of equations (7) for a certain k ≥ 3, the truth for k + 1 follows. But for k = 3 the equations (7) are true, and consequently the equalities are established for all k ≥ 3.
We shall now show that the difference of neighboring convergents δk - δk-1 satisfies the relation
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (8)
Indeed,
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
Using equations (7) we transform the numerator of this new fraction:
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
The expression in the parentheses may be obtained from the original one by replacing k by k - 1. Repeating this transformation for the new expression, we evidently obtain the chain
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
Whence it follows that
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
If the expansion of a/b into a continued fraction has n terms, then the nth convergent δn coincides with a/b. Applying (8) when k = n yields
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (9)
We return to the solution of the equation
ax + by + c = 0, (a, b) = 1. (10)
We rewrite the relation (9) in the form
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
Reducing this to a common denominator and rejecting it, we obtain
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]
(Continues…)
Excerpted from "The Solution of Equations in Integers"
by .
Copyright © 2018 Dover Publications, Inc..
Excerpted by permission of Dover Publications, Inc..
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.
