Express the HCF of 1232 and 573 as 1232x + 573y = 1

HOME

Math Central

Quandaries & Queries

Question from Anonymous, a student:

I asked about my question to everyone online but they haven't answered
probably. So, I decide to ASK you about this problem!

Here goes: Express the HCF of 1232 and 573 as 1232x + 573y = 1.

(I found this from the website:
http://www.math.mtu.edu/mathlab/COURSES/holt/dnt/euclid4.html)

Remember that something looks like this . but it is a multiplication sign.

1. 1232 = 2 ·573 + 86.
2. 573 = 6 ·86 + 57.
3. 86 = 1 ·57 + 29.
4. 57 = 1 ·29 + 28.
5. 29 = 1 ·28 + 1.
6. 28 = 28 ·1 + 0.

Then, do the reverse:
1 = 29 – 1 times 28
a. = 29 – 1 ·(57 – 1 ·29)
b. = –1 ·57 + 2 · 29
c. = –1 ·57 + 2 ·(86 – 1 ·57)
d. = 2 ·86 – 3 ·57
e. = 2 ·86 – 3 ·(573 – 6 ·86)
f. = –3 ·573 + 20 ·86
g. = –3 ·573 + 20 ·(1232 – 2 ·573)
h. = 20 ·1232 – 43 ·573.

from the line b, how do you get that? What do I have to multiple or add or what?

Thankyou, I hope this isn't much of too tiring to you.
From Anonymous.

Dear Anonymous,

What happens is that each equation 1, 2, ..., 6 is solved for its remainder term and then the result is substituted into the one among b, c, ... that you're working on. These equations are used in t he order 5, 4, 3, 2, 1

The first equation you have is equation 5 re-written. To get from it to a b, you re-write equation 4 as 28 = 57 - 1x29 and substitute that for 28. Then you simplify in order to get c. Next you rewrite 3 as 29 = 86-1x57 and substitute that for 29 in what you have. Simplify, then repeat by solving equation 2 for 57, then simplify again and do the same using equation 1 and 86. When you're done, everything is in terms of 1232 and 573.

Hope this helps.
Victoria

Math Central is supported by the University of Regina and The Pacific Institute for the Mathematical Sciences.