PROBLEM LINK:PREREQUISITES:Greatest common divisors. Problem:Given a , b , c in the equation ax+by=c; The problem is to determine if there exists at least one solution for some integers value of x and y where x, y may be negative or nonnegative integers. Explanation:We can show this like this: [ax + by = c] has integer solution x0,y0 implies GCD(a,b)/c. Factoring out GCD(a,b) from each side gives [\frac{1}{GCD(a,b)}(ax+by) = \frac{1}{GCD(a,b)}c] which must still have an integer solution as GCD(a,b) obviously divides both a and b. If GCD(a,b) does not divide c there is no integer solution.
asked 12 May '15, 00:07

what about a=4,b=5 and c=6?? GCd(4,5)=1 and 6 divides 1. but it has no solution . ie, no integral values of x and y satisfy the equation . answered 03 Mar '16, 23:57
