Hi,
I am having trouble getting my head around this problem :
Use the euclidean algorithim to determine gdc (350,196)
I understand that the gdc is the largest number that divides both without leaving a remainder but i cant understand how to actually work it out without being really confused
Can anyone help me out?
The Euclidian Algorithm is fundamentally an effective method for determining the greatest common divisor/factor of two numbers, a and b, expressed as g.c.d.(a,b). It is also an effective tool in solving linear indeterminate algebra problems. The detailed derivation and proof of the method is much too long to present here and I refer you to any good book on Number Theory to obtain an understanding of its background and derivation.
The algorithm process is based on the fact that if two numbers have a common factor/divisor "f", then f is also a factor/divisor of their difference. We can express the two numbers by af and bf making their difference af - bf or (a - b)f. Consider the two numbers 148 and 50. Their difference being 78 means that any common factor of 148 and 50 also divides 78. Now consider the 78 and 50. Their difference being 28 means that any common factor of 78 and 50 also divides 28. Continuing this process, we travel through 50 - 28 = 22, 22 - 6 = 16, 16 - 6 = 10, 10 - 6 = 4, 6 - 4 = 2, 4 - 2 = 2, and 2 - 2 = 0. Therefore, the g.c.f.(148,50) = 2, the last remainder before reaching the zero remainder. Euclid realized that this could be shortened by dividing the two numbers and then working with only the remainder. The final technique involves successive divisions and determination of remainders until no remainder exists. Each successive step of the process results in a smaller remainder until a zero remainder is reached. The remainder immediately preceding the zero remainder is the greatest common divisor. Thus, for our first example, 148 = 50(2) + 48; 50 = 48(1) + 2; 48 = 24(2) + 0, indicating that the g.c.f(148,50) = 2.
Consider the example of (11, 31). 31 = (11)2 + 9; 11 = (9)1 + 2; 9 = 2(4) + 1; 1 = (1)1 + 0; thus g.c.f.(11, 31) = 1
Take the less obvious case of (231, 951).
951 = (231)4 + 27;
231 = (27)8 + 15
27 = (15)1 + 12
15 = (12)1 + 3
12 = (3)4 + 0
Therefore, g.c.f.(231, 951) = 3.
The prime factors of 231 are 3^1, 7^1, and 11^1, meaning 231 has (1+1)(1+1)(1+1) = 8 factors all together; 1, 3, 7, 11, 21, 33, 77, & 231, its aliquot divisors being 1, 3, 7, 11, 21, 33, and 77.. The prime factors of 951 are 3^1 and 317^1, meaning 951 has (1+1)(1+1) = 4 factors all together; 1, 3, 317, and 951, its aliquot divisors being 1, 3, and 317. Clearly, the greatest common factor/divisor is 3.
The total number of divisions required in using the algorithm is at most 5 times the number of digits in the smallest number.
Its application to solving linear indeterminate algebra problems is illustrated by the following examples 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.
This has led us to but one solution however. The general solution is x = 3420 + 45t and y = -1440 - 19t where t equals any positive or negative integer which leads us to:
t..............1...........5..........10.........etc.
x...........3465.....3645......3870.......
y..........-1459....-1535.....-1630......
19x.......65835...69255....73530.....
45y......-65655..-69075...-73350.....
Diff........180.......180........180........
It is often required to find only positive integer answers to a given problem. If we sought positive integer answers to this problem, they would have to lie between (-3420/45) < t < (-1440/19) or -76 < t < -75.789. Clearly, there is no integral value of t between these two limits thereby showing that there are no positive integral answers to this particular problem.
A better view of the usefulness of the method can best be obtained from a more typical example from the field of recreational mathematics. A hardware store owner wants to clear out his inventory of three old tools. He has a total of 100 tools. In order to at least break even, he wants to take in a minimum of $1318.00. He decides to sell the tools at $5.00, $16.00, and $24.00. How many of each tool must he sell in order to achieve his goal of $1318.00 in sales?
1--Lets call the three tools x, y, and z.
2--Then, x + y + z = 100
3--Also, 16x + 24y + 5z = 1318
4--Multiplying (2) by 5 and subtracting from (2) yields
...16x + 24y + 5z = 1318
....5x + 5y + 5z = 500
...11x + 19y = 818
5--Since g.c.d.(11,19) = 1 divides 818, we know there are integral answers.
6--We first reduce the problem to 11x + 19y = 1
7--Applying the Euclidian Algorithm, we have
...19 = 1(11) + 8 or 8 = 19 - 1(11)
...11 = 1(8) + 3 or 3 = 11 - 1(8)
...8 = 2(3) + 2 or 2 = 8 - 2(3)
...3 = 1(2) + 1 or 1 = 3 - 1(2)
...2 = 1(1) + 0 making the obvious g.c.d.(11,19) = 1
7--Working backwards
...1 = 3 - 1(2) = 3 - 1(8) + 2(3) = 3(3) - 1(8)
...1 = 3(3) - 1(8) = 3(11) - 3(8) - 1(8) = 3(11) - 4(8)
...1 = 3(11) - 4(8) = 3(11) - 4(19) + 4(11) = 7(11) - 4(19)
8--Therefore, the x and y values that satisfy 11x + 19y = 1 are x = +7 and y = -4.
9--The values of x and y that now satisfy 11x + 19y = 818 are x = 7(818) = 5726 and y = -4(818) = -3272.
10--The general solution leading to an infinite number of integral answers is x = 5726 + 19t and y = -3272 - 11t.
11--Our problem clearly requires positive integral solutions which can only derive from -(5726/19) < t < -(3272/11) or -301.368 < t < -297.454.
12--Therefore, we have positive integral solutions for t = -298, -299, -300, and -301.
13--The positive solutions are then
...t.....-298.....-299.....-300.....-301
...x......64........45........26........7
...y.......6.........17........28.......39
14--From x + y + z = 100, we can now derive the z values as
...t.....-298.....-299.....-300.....-301
...x......64........45........26........7
...y.......6.........17........28.......39
...z......30........38........46.......54
15--Therefore, the store owner has four possible sales scenarios that will allow him to take in $1318.00.
16--Checking:
...For t = -298, 16(64) + 24(6) + 5(30) = 1024 + 144 + 150 = $1318.
...For t = -299, 16(45) + 24(17) + 5(38) = 720 + 408 + 190 = $1318
...For t = -300, 16(26) + 24(28) + 5(46) = 416 + 672 + 230 = $1318
...For t = -301, 16(7) + 24(39) + 5(54) = 112 + 936 + 270 = $1318
The other powerful method for solving linear indeterminate algebra problems is the method of repeated reductions, so named as the objective of the method is to reduce the given expression to one where one of the coefficients is unity. Why this is necessary is best illustrated by the following example.
Given the expression x + 11y = 45. This can be rewritten as x = 45 - 11y. Clearly, any value of y will produce a corresponding value of x, indicating the existance of an infinite number of solutions, both positive and negative. If, however, we are only interested in positive integral solutions of x and y, we can immediately observe that y must be greater than 0 and less than 45/11 = 4.0909. Therefore, y = 1, 2, 3, and 4 will produce positive integer answers of x = 34, 23, 12, and 1 for corresponding values of y = 1, 2, 3, and 4. This tells us that if either of the coefficients of our two terms is unity, we can easily find our way to the immediate solutions.
Take the simple expression of 2x + 5y = 37. solving for x, we find x = (37 - 5y)/2 = 18 + 1/2 - y - y/2 = 9 - y - (y - 1)/2. Again, there are an infinite number of integral positive and negative solutions but let us seek out the positive integer solutions. For positive integer solutions, (y - 1)/2 must be a positive integer so let (y - 1)/2 = k making y = 2k + 1.
Substituting this back into our original expression yields us 2x + 5(2k + 1) = 2x + 10k + 5 = 37 or x = 16 - 5k.
We now have two expressions in x and y with unit coefficients in terms of the positive integer values of k.
By inspection, k can be any value from 0 through 3 giving us positive integers solutions of
k.....0.....1.....2.....3
x....16...11....6.....1
y.....1.....3....5.....7
Armed with this information, we will now pursue the organized series of steps in solving such expressions.
Take our hardware store problem from earlier in this discussion from which we still seek positive integer answers. The first 4 steps are identical and are repeated here for completness.
1--Lets call the three tools x, y, and z.
2--Then, x + y + z = 100
3--Also, 16x + 24y + 5z = 1318
4--Multiplying (2) by 5 and subtracting from (2) yields
...16x + 24y + 5z = 1318
....5x + 5y + 5z = 500
...11x + 19y = 818
5--Divide through by the lowest coefficient, 11, yielding 1x + 1y + 8y/11 = 74 + 4/11
6--Rearranging, (8y - 4)/11 = 74 - x - y.
7--(8y - 4)/11 must be an integer but we need to reduce the coefficient of y to unity.
8--By observation, we can multiply (8y - 4)/11 by 7 and redivide by 11
9--(56y - 28)/11 = 1y + y/11 - 2 - 6/11
10--Again, (y - 6)/11 must equal an integer k making y = 11k + 6.
11--Substituting (10) back into (1) yields 11x + 209k + 114 = 818 or x = 64 - 19k.
12--By inspection, k can be any value from 0 through 3 yielding
...k.....0.....1.....2.....3
...x....64...45...26.....7
...y....6.....17...28...39 Look familiar?
Ii think you will agree that both methods are relatively simple and straight forward, the repeated reductions method probably being somewhat simpler and less time consuming. The Euclidian Algorithm method is probably better suited for problems involving large numbers rather than the simpler numbers used in these examples.
A distinct advantage of the repeated reductions method is that it can be applied to problems resulting in one expression with more than 2 unknowns. The following example will illustrate.
Joe came back from a stamp collectors gathering and told his sister, Jill, that he bought a hundred stamps. Joe said he bought the stamps at four different prices: $0.59, $1.99, $2.87, and $3.44 each. Jill asked, "How much did you pay altogether?" Joe replied, "One hundred dollars exactly." How many stamps did Joe buy at each
price?
Given: (1)--W + X + Y + Z = 100 and (2)--.59W + 1.99X + 2.87Y + 3.44Z = 100.
1--Multiply (2) by 100--->59W + 199X + 287Y + 344Z = 10000. (3)
2--Multiply (1) by 59----->59W + 59X + 59Y + 59Z = 5900. (4)
3--Subtract (4) from (3)--->140X + 228Y + 285Z = 4100. (5)
4--Divide (5) through by 140--->X + Y + 88Y/140 + 2Z + 5Z/140 = 29 + 40/140.
5--Solving for X = 29 - Y - 2Z - (88Y + 5Z - 40)/140. (6)
6--Set (88Y + 5Z - 40)/140 = u = an integer.
7--Rearranging, 140u = 88Y + 5Z - 40. (7)
8--Dividing (7) through by 5--->28u = 17Y + 3Y/5 + Z - 8. (8)
9--Solving for Z, Z = 28u - 17Y - 3Y/5 + 8. (9)
10--With 3Y/5 = integer, multiply by 2 yielding 6Y/5. (10)
11--Dividing (10) out yields 6Y/5 = Y + Y/5 where Y/5 must be an integer also.
12--Set Y/5 = v whence Y = 5v. (11)
13--Substituting (11) into (8)--->Z = 28u - 85v - 3v + 8 = 28u - 88v + 8. (12)
14--Substituting (11) and (12) into (6)--->X = 29 - 5v -56u + 176v -16 - (440v + 140u - 440v + 40 - 40)/140. (13)
15--Simplifying (13)--->X = 29 - 5v -56u + 176v - 16 - u = 13 + 171v - 57u. (13)
16--Substituting (11), (12), and (13) into (1)---> W + 13 + 171v - 57u + 5v + 28u - 88v + 8 = 100. (14)
17--Simplifying (14)---> W = 29u - 88v + 79. (14)
18--From (11) v =/> 1 and from (12) u =/> 3.
19--Trying v = 1 and u = 3, W = 78, X = 13, Y = 5, and Z = 4.
20--Checking--->78 + 13 + 5 + 4 = 100. Okay.
21--Checking--->78(.59) + 13(1.99) + 5(2.87) + 4(3.44) = 46.02 + 25.87 + 14.35 + 13.76 = 100. Okay.
22--Trying v = 2 and u = 3, X = 184 exceeding total of 100, therefore invalid.
23--Trying v = 1 and u = 4, X = negative number, therefore invalid.
24--All other values of u and v produce invalid results.
25--Therefore W = 78, X = 13, Y = 5, and Z = 4 is the only solution. QED!
I hope this has been of some interest, to you. If you are at all interested in exploring the derivation and methods for solving single equations with two or more unknowns, I offer you the following references:
1--Number Theory and its History--by Oystein Ore--Dover Publications, Inc., 1976. *
2--Mathematical Brain Teasers--by J.A.H. Hunter--Dover Publications, Inc., 1976
3--Mathematics for the Nonmathemetician by Morris Kline, Dover Publications, Inc., 1985.
4--Recreations in the Theory of Numbers by Albert H. Beiler, Dover Publications, Inc., 1964.
5--An Adventurer's Guide to Number Theory by Richard Friedberg, Dover Publications, Inc., 1968.
6--Excursions in Number Theory by C. Stanley Ogilvy and John T. Anderson, Dover Publications, Inc., 1988.
7--Elementary Theory of Numbers by William J. LeVeque,, Dover Publications, Inc., 1990.
8--Fundamental Concepts of Algebra by Bruce E. Meserve, Dover Publications, Inc., 1982.
(Dover Publications, Inc., Mineola, NY.)
