Usu's blog

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
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

For finding the solution (provided it exists) you can use the extended Euclid algorithm. It is explained quite well here

In case you are looking for a non-recursive implementation (and an alternative explanation) check this

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

Thank you!

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