Usu's blog

Extended Euclidian Algorithm

By Usu, history, 6 years ago, In English

Hey guys, can anybody explain me well how can we find (and when we can't find) (x,y) such a*x + b*y = c?

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
6 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Here is the complete reference : http://www.diva-portal.org/smash/get/diva2:530204/FULLTEXT01.pdf

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Left side of the equation is a multiple of gcd(a, b), hence c has to be a multiple of gcd(a, b) as well. Now, proving that a solution exists whenever c is a multiple of gcd(a, b) can be done using Bezout Identity https://brilliant.org/wiki/bezouts-identity/

For finding the solution (provided it exists) you can use the extended Euclid algorithm. It is explained quite well here https://www.geeksforgeeks.org/euclidean-algorithms-basic-and-extended/

In case you are looking for a non-recursive implementation (and an alternative explanation) check this https://brilliant.org/wiki/extended-euclidean-algorithm/

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you!

→ Reply
»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I am assuming a and b are positive integers, and you only want integer x and y. If a and b are not positive you can just multiply by -1 at end of this method.

This is how I do it, it's not most efficient way but it's in my opinion a very clear and easy way to remember.

ax + by = c works when c is a multiple of gcd(a,b)

Be careful of cases where a = 0 or b = 0 or both

So you just need to find the (x,y) such that ax + by = gcd(a,b) and then multiply that by c/gcd(a,b) to get x and y such that ax + by = c.

To solve the above answer, we can make observation that a mod b = a — kb where k = floor(a/b).

Now there are two base cases we know:

ax + by = a //in this case x = 1, y = 0

ax + by = b //in this case x = 0, y = 1

be careful though, in the case where a = b because you might assign x = 1 AND y = 1, where you only mean to assign one of them.

Every other case can be solved from the base case, up until gcd(a,b) in the following manner:

let's say x[i] and y[i] store x,y values such that a*x[i] + b*y[i] = i

building from our known x[a]=1,y[a]=0, x[b]=0, y[b]=1 (shown above) solution we want to find x[a mod b] and y[a mod b]

since a — kb = a mod b

x[a] — k*x[b] = x[a — kb] = x[a mod b]

similarily y[a] — k*y[b] = y[a mod b]

now we keep finding new x and y values until we reach gcd(a,b) and we are done

→ Reply