Reference no: EM131572902

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

x₁ = x₀ + [b/(gcd(a, b)]t and y₁ = y₀ - [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

x₁ = x₀ + [b/(gcd(a, b)]t and y₁ = y₀ - [a/(gcd(a, b)]t