Question: Use Theorem to prove that for all integers a, c, and n with n > 1, if gcd(a, n) = d and d divides c, then the congruence ax ≡ c (mod n) has a solution.
Theorem: Solving a Diophantine Equation of the Form ax + by = c
Consider the equation ax + by = c, where a, b, and c are integers and α and b are both nonzero.
1. If the greatest common divisor of α and b is a divisor of c, then there are integers x1 and y1 so that the pair (x1, y1) is a solution for ax + by = c.
2. If ax + by = c has a solution in integers, then the greatest common divisor of α and b is a divisor of c.
3. If the pair (x0, y0) is a particular solution for ax + by = c and if t is any integer, then the pair (x1, y1) is also a solution, where
x1 = x0 + [b/(gcd(a, b)]t and y1 = y0 - [a/(gcd(a, b)]t
4. If the pair (x0, y0) is a particular solution for ax + by = c and (x1, y1) is any solution, then there exists an integer t so that
x1 = x0 + [b/(gcd(a, b)]t and y1 = y0 - [a/(gcd(a, b)]t