Usu's blog

By Usu, history, 6 years ago,

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?

• +1

 » 6 years ago, # | ← Rev. 2 →   +1 Here is the complete reference : http://www.diva-portal.org/smash/get/diva2:530204/FULLTEXT01.pdf
 » 6 years ago, # |   +1 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/
 » 6 years ago, # |   0 Thank you!
 » 6 years ago, # |   +6 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 bothSo 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 = 0ax + by = b //in this case x = 0, y = 1be 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] = ibuilding 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 bx[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