Another example

Usually to find the GCF we use Euclidean algorithm. To express the GCF of 720 and 230

720= 230*3 +30
230=30*7 +20
30=20*1 +10
20=10*2 +0

When we get a zero in the "remainder" spot, we are done. The gcd is the previous remainder. So, in this case, the GCF of the numbers 720 and 230 is 10.

One of the things that Euclid showed is that we can express gcd(a,b) as a linear combination of a and b. That is, there always exist integers x and y such that ax + by = d, where d = gcd(a,b).

This is getting closer to what we want.

The way to find the integers x and y is to use the Euclidean algorithm in reverse.

Now we have to go back and express 10 in terms of the diferent factors we already found usind Euclidean algorithm

Let's go to 10

Solve for the gcd:

10 = 30-20*1

Now look at the next line up in our Euclidean algorithm:

230=30*7 +20

Solve this for the remainder: 20 = 230-30*7. Now substitute this
expression of the number 20 into the last line we had: 10 = 30-20*1

10 = 30-20*1

10 = 30-1*(230-30*7)

10 = 30-230+30*7

10=30*8-230

10=(720-230*3)*8-230

10=8*720-230*24-230

10=8*720-230*25

We have found the desired integers.

Other example

If we want to express

49x+17y= 13

17=15*1+2

15=2*7+1

7=7*1+0

Our last residue is 1. So 1 is our GCF

now we have to go and make the substitutions back

1=15-2*7

1=15-7(17-15*1)

1=8*15-17*7

1=8(49-17*2)-7*17

1=8*49-8*17*2-7*17

1=8*49-23*17

To check soluctions we can use this web page