| |
Name: Murray
Who is asking: Student
Level: Secondary
Question:
Can you please explain to me why the euclidean algorithm works? Thanks alot.
Hi Murray,
The idea is simple if we understand that when something is true of one side
of an equation then it is true of the other side also. Let us illustrate by
trying to find d, the gcd of 12378 and 3054.
Write
12378 = 4 x 3054 + 162 (equivalently 12378 - 4 x 3054 = 162)
and note that if d | 12378 (this means d divides 12378) and d | 3054 then it
must be that d | 162 ( if d divides the left hand side of the equation then
it must divide the right hand side, but if d is the gcd of 12378 and 3054 we
already are assuming that it divides 12378 and 3054, so that d | 162). How
does this help? What it tells us is that the gcd of 12378 and 3054 is the
same as the gcd of 3054 and 162, i.e. we have reduced the problem to one
dealing with smaller numbers. We thus can repeat the process and write
3054 = 18 x 162 + 138
and conclude that we want the gcd of 162 and 138. Repeating we write
162 = 1 x 138 + 24
138 = 5 x 24 + 18
24 = 1 x 18 + 6
18 = 3 x 6 + 0.
The last non-zero remainder, 6 in this case, is the required gcd. (This is
so since it is clear that 6 is the gcd of 6 and 18 and thus is the gcd is 18
and 24 and thus is ... the gcd of 3054 and 12378.
Cheers,
Penny
Go to Math Central
|
|