# Thread: Euclidean algorithm question help

1. ## [Solved, thanks Opalg :D] Euclidean algorithm question help

Q: Find the HCF of the pair and express it in the form xa + yb = h

966 and 1633

I can find the HCF quite easily. I stuff up when "cleaning up" the equation.
First of all: The final answer to this question is 23 = 22x966-13x1633

My answer is different and here is how I got it:

I got a HCF of 23 and by using the euclidean algorithm. I then showed:

[..]Thus 966 = 1633 - 1x966 [1]
667=966 - 1x667 [2]
598=667 - 2x299 [3]
276=299 - 4x69 [4]

I now tried to express it in the form xa + yb = h

23=299 - 4x69 [from 4]
=299 - 4(667 - 2x299) [from 3]
=3x299 - 4x667
=3(966 - 1x667) - 4x667 [from 2]
=3x966 - 7x667
=3x966 - 7(1633 - 1x966)
Therefore =11x966 - 7x1633

Now that is obviously wrong, but I don't know where or how the mistake I made occurred. I hate when I spend ages on a question and it turns out wrong. It lowers my self esteem

2. Originally Posted by RAz
Q: Find the HCF of the pair and express it in the form xa + yb = h

966 and 1633

I can find the HCF quite easily. I stuff up when "cleaning up" the equation.
First of all: The final answer to this question is 23 = 22x966-13x1633

My answer is different and here is how I got it:

I got a HCF of 23 and by using the euclidean algorithm. I then showed:

[..]Thus 667 = 1633 - 1x966 [1]
299=966 - 1x667 [2]
69=667 - 2x299 [3]
23=299 - 4x69 [4]

I now tried to express it in the form xa + yb = h

23=299 - 4x69 [from 4]
=299 - 4(667 - 2x299) [from 3]
=9x299 - 4x667
=9(966 - 1x667) - 4x667 [from 2]
=9x966 - 13x667
=9x966 - 13(1633 - 1x966)
Therefore =22x966 - 13x1633

Now that is obviously wrong, but I don't know where or how the mistake I made occurred. I hate when I spend ages on a question and it turns out wrong. It lowers my self esteem
The method is correct, it's just the arithmetic that is all wrong. See corrections in red above.

3. Thankyou for your help, this is very useful