The application of the Euclidian Algorithm to solving linear indeterminate algebra problems is illustrated by the following example but first let us review some fundamental facts.
1--If "a' and "b" are positive integers other than zero, and "a" divided by "b" (a/b) is an integer, it is said that "b" divides "a" or "b" is a divisor of "a". This is expressed by b I a ("b" followed by a vertical line followed by "a") meaning that "b" divides "a".
2--If "a" and "b" are positive integers other than zero, there is a singularly unique integer "d" = g.c.d.(a,b) (the greatest common divisor of a and b). Stated another way, for there to be integers x and y that satisfy the expression ax + by = c, it is necessary that d I c (d divides c) where d = g.c.d.(a,b).
3--A positive integer "p" is said to be prime if, and only if, its only positive divisors are 1 and "p".
4--The numbers "a" and 'b" are said to be relatively prime if g.c.d.(a,b) = 1.
The expression ax + by = c, "a" and "b" relatively prime, has positive integer solutions if d = g.c.d.(a,b) divides "c". If the g.c.d.(a,b) = d, d must divide c evenly for integral solutions.
With x' and y' as a known solution of ax + by = c, other solutions are derivable from x' = x + bt/d and y' = y - at/d where t = any integer, positive or negative.
When a and b are relatively prime, integer solutions exist for ax + by = c.
The expression ax + by = c may be solved by first solving ax + by = 1.
If x' and y' are integer solutions for ax + by = 1, then x' = cx and y' = cy are solutions for ax + by = c.
If there is one solution, there are an infinite number of solutions.
The other solutions derive from x" = x' + bt and y" = y' - at.
Determining the unknown quantities in expressions of this type are often complicated when there are no boundries to the problem. You must know whether you are seeking positive integer solutions, integer solutions, either positive or negative, or simply rational solutions?
Now for an example of the method. I will go through the process but with limited explanation, relying on your own efforts to seek out the derivation of the method.
1--Given 19x + 45y = 180. Solve for all integer answers.
2--Since g.c.d.(19,45) = 1, which divides 180, there are integer answers.
3--We first simplify this to 19x + 45y = 1.
4--We now go through the Euclidean Algorithm process.
5--45 = 19x2 + 7 or 7 = 45 - 2x19
....19 = 7x2 + 5 or 5 = 19 - 2x7
.....7 = 5x1 + 2 or 2 = 7 - 1x5
.....5 = 2x2 + 1 or 1 = 5 - 2x2
.....2 = 1x1 + 0 thus showing that the g.c.d.(19,45) = 1.
Working backwards with these expressions:
6--Substituting 2 = 7 - 1x5 into 1 = 5 - 2x2 we get 1 = 3x5 - 2x7
7--Substituting 5 = 19 - 2x7 into 1 = 3x5 - 2x7 we get 1 = 3x19 - 8x7
8--Substituting 7 = 45 - 2x19 into 1 = 3x19 - 8x7 we get 1 = 19(19) - 45(-8)
9--Thus, values of x and y that satisfy 19x + 45y = 1 are x = 19 and y = - 8.
10--Checking, 19(19) + 45(-8) = 361 - 360 = 1.
11--The values of x and y satisfying our original equation are therefore x = 180(19) = 3420 and y = 180(-8) = -1440.
12--Checking, 19(3420) + 45(-1440) = 64,980 - 64,800 = 180.
Using your numbers:
3647s + 1841r = 1
3647 = 1(1841) + 1806
1841 = 1(1806) + 35
1806 = 51(35) + 21
35 = 1(21) = 14
21 = 1(14) = 7
14 = 2(7) + 0
Therefore, the g.c.d. of 3647 and 1841 is 7.
Since 7 does not evenly divide 1, there are no integer solutions.
Working backwards yields 3647(105) - 1841(208) = 7 or 521(105) - 263(208) = 1.
If both 105 and 208 were evenly divisible by 7, there would be a solution.
