Express in linear combination

R. Bharathi

Express the HCF of 72,124 in the linear combination of 72,124.
Please use Euclid's Algorithm.

Reply 1

NotNotBatman

Original post by R. Bharathi

Express the HCF of 72,124 in the linear combination of 72,124.
Please use Euclid's Algorithm.

So, use Euclid's Algorithm, what's the problem ?

Reply 2

R. Bharathi

I'm stuck with three terms at the end. I got 72x and 124y, but also a constant, which I don't know what to do with

Original post by NotNotBatman

So, use Euclid's Algorithm, what's the problem ?

Reply 3

RDKGames

Study Forum Helper

Original post by R. Bharathi

I'm stuck with three terms at the end. I got 72x and 124y, but also a constant, which I don't know what to do with

Huh? Just post your working out as then its easier to see what you mean!

The process here is to literally just use EA to obtain the last non-zero remainder (the HCF), and then work backwards so that at the end you have:

72x + 124y = HCF(72,124)

where x,y are known.

(edited 5 years ago)