Problem #PRU-60489

Problems Algebra and arithmetic Number theory. Divisibility Equations in integer numbers Methods Extremal principle Extremal principle (other) Methods from geometry Geometric interpretations in algebra Pigeonhole principle Pigeonhole principle (other) The greatest common divisor (GCD) and the least common multiplier (LCM). Mutually prime numbers
 13–15  4.0

Problem

Let \(a\), \(b\), \(c\) be integers; where \(a\) and \(b\) are not equal to zero.

Prove that the equation \(ax + by = c\) has integer solutions if and only if \(c\) is divisible by \(d = \mathrm{GCD} (a, b)\).