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?

# | User | Rating |
---|---|---|

1 | tourist | 3843 |

2 | jiangly | 3705 |

3 | Benq | 3628 |

4 | orzdevinwang | 3571 |

5 | Geothermal | 3569 |

5 | cnnfls_csy | 3569 |

7 | jqdai0815 | 3530 |

8 | ecnerwala | 3499 |

9 | gyh20 | 3447 |

10 | Rebelz | 3409 |

# | User | Contrib. |
---|---|---|

1 | maomao90 | 171 |

2 | adamant | 163 |

2 | awoo | 163 |

4 | TheScrasse | 157 |

5 | nor | 153 |

6 | maroonrk | 152 |

6 | -is-this-fft- | 152 |

8 | Petr | 145 |

9 | orz | 144 |

9 | pajenegod | 144 |

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?

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/17/2024 22:51:43 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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

Left side of the equation is a multiple of

gcd(a,b), hencechas to be a multiple ofgcd(a,b) as well. Now, proving that a solution exists whenevercis a multiple ofgcd(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/

Thank you!

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