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