Problem #PRU-60489

Problems Algebra 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) GCD and 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)\).