divided throughout by that factor. In what follows it will therefore be supposed that a and b are prime to one another. 393. To shew that integral values can always be found which will satisfy the equation ax + by = c, provided a and b are prime to one another. α Let be reduced to a continued fraction, and let b cq, y = Hence it follows from (i) that either x = cq, y=cp or x = - cq, y - cp is a solution of the equation ax — by = c ; and from (ii) that either x = cp or x = cq, y = cp is a solution of the equation ax + by = c. Hence at least one set of integral values of x and y can always be found which will satisfy the equation ax + by = C. The above investigation fails when a or b is unity. But the equation ax + y = c is obviously satisfied by the values x = =a, ± y = c − aa, where a is any integer. So also xby=c is satisfied by the values x = c + bß, y = ß, where B is any integer. Hence the equation ax + by = c always admits of at least one set of integral values. 394. Having given one set of integral values which satisfy the equation ax - by = c, to find all other possible integral solutions. Let x=a, y=B be one ax - by = c; then az - bß = c. solution of the equation Hence, by subtraction, Now since a divides a (x-1), it must also divide b(y – B); a must therefore be a factor of y - ẞ, since it is prime to b. Let then yẞ=ma, where m is any integer; then a (x − a) = mba, and therefore x=a+mb. Hence, if x = a, y = ẞ be one solution in integers of the equation ax-by= c, all other solutions are given by x = a+mb, y=B+ma, where m is any integer. It is clear from the above that there are an indefinite number of sets of integral values which satisfy the equation ax - by = c, provided there is one such set; and, from the preceding article, we know that there is one set of integral values. It is also clear that, whether a and B are positive or not, an indefinite number of values can be given to m which will make a + mb and ẞ + ma both positive. Hence there are an infinite number of positive integral solutions of the equation ax - by = c. 395. Having given one set of integral values which satisfy the equation ax + by = c, to find all other possible integral solutions. Let xa, y=B be one integral solution of the equation ax + by = c; then ax + bß = C. Hence, by subtraction, a (x - a) + b (y − B) = 0. Now, since a divides a (x − a), it must also divide b(y-B); a must therefore be a factor of yẞ, since it is prime to b. Let then y-8=ma, where m is any integer; then a (x − a) = − b (y — B) = — mab; and therefore x = a - mb. Hence, if x = a, y =ẞ be one solution in integers of the equation ax - by = c, all other integral solutions are given by x = a— mb, y = ß + ma, where m is any integer. S. A. 32 From the above, together with Art. 393, it follows that there are an indefinite number of sets of integral values which satisfy the equation ax + by = c. The number of positive integral solutions of the equation is, however, limited in number. 396. To find the number of positive integral solutions of the equation ax + by = c. We have proved in Art. 393, that the equation ax + by = c is satisfied by the values x = cq, y=- cp, or by the values = cq, y=cp, where p/q is the penultimate convergent to a/b. First suppose that acq, y=-cp satisfy the equation; then all other integral values which satisfy the equation are given by where m is any integer. .(i), From (i) it is clear that in order that x and y may both be positive, and not zero, m must be a positive integer, and that the greatest permissible value of m is I (2) and its least value I (CP)+1, so that the number of set of values of x and y corresponds to each value of m, the number of solutions is I cq (7) − 1 (2). с I2+f2; then a α ab a (cq) — b (cp) ab is 1-1, or I1- I,- 1 according as f, is not or is less than f 2 C 2 + 1 or 2 I (ab) according as the fractional part of is or is not less than the fractional part of p α It can be shewn in a similar manner that if x = − cq, y=cp satisfy the equation, the number of solu tions in positive integers is I (+1 or I ab according Ex. 1. Find the positive integral values of x and y which satisfy the equation 7x-13y=26. We have == 7 13 1 the penultimate convergent is therefore 1 Then 7.2-13.1=1; ... 7 (2 × 26) – 13 (26) = 26. 2 Hence one solution is x=52, y = 26; the general solution is thereforex=52+ 13m, y=26+7m. [In this case the solution x=0, y= 2 can be seen by inspection; and hence the general solution is x=13m, y=-2+7m, which is easily seen to agree with the previous result.] Ex. 2. Find the positive integral values of x and y which satisfy the equation 7x+10y=280. 7 1 1 1 the penultimate convergent being 7.3-10.2=1; .. 7 (3.280) + 10 (−2.280) = 280. Hence x=840, y=-560 is one solution in integers. The general solution in integers is therefore x=840-10m, y=560+7m; and, in order that x and y may be positive m84 and m 480. Thus the only values are x=40, y=0; x= =30, y=7; x=20, y=14; x=10, y=21; x=0, y = 28. Ex. 3. Find the number of solutions in positive integers of the equation 3x+5y=1306. 3 Here = 5 1 1 1 .. 3. (2 × 1306) +5 (1306) = 1306. Hence the general solution is x= =2612-5m, y=3m-1306. For positive values of x and y we must have m> 435 and m⇒ 522. 397. Integral solutions of the two equations can be obtained as follows. Eliminate one of the variables, z suppose; we then have the equation (ac' — a'c) x + (bc' — b'c) y = dc' — d'c...............................(i), and this equation has integral solutions provided ac' - a'c and bcb'c are prime to one another, or will become prime to one another after division by any common factor which is also a factor of dc' - d'c. Hence from (i) we obtain, as in the preceding articles, the general solution x = a + (bc' — b'c) n, y = ẞ — (ac' — a'c) n, where x=a, y=ß is any integral solution, and n is any integer. Now substitute these values of x and y in either of the original equations: we then obtain an equation of the form Az+Bn=C, from which we can obtain integral solutions of the form z=y+ Bm, n = 8- Am, provided A and B are prime to one another, or will become so after division by any common factor which is also a factor of C. Ex. Find integral solutions of the simultaneous equations 5x+7y+2z=24, 3x-y-42=4. Whence Eliminating z, we have 13x+13y=52, or x+y=4. x=2+n, y=2-n. Then 5 (2+ n) +7 (2 − n) + 2z=24, that is 2 - n=0. Hence the general solution is x=2+n, y=2-n, z=n. If x, y and z are to be positive, the only solutions are x=4, y=0, z=2; x=3, y=1, z=1; and x=2, y = 2, z=0; and, if zero values are excluded, there is only one solution, namely x=3, y=1, z=1. 398. The following are examples of some other forms of indeterminate equations. Other cases will be found in Barlow's Theory of Numbers. Ex. 1. Find the positive integral solutions (excluding zero values) of the equation 3x+2y+8z=40. It is clear that z cannot be greater than 4, if zero and negative values of x and y are inadmissible. |