Linear Diophantine equations
Linear Diophantine equations are of the form
ax + by = c
where a,b,c ∈ ℤ. We want to ascertain whether the equation admits integer solutions, that is solutions (x, y) ∈ ℤ. If we omit the trivial case where a or b is equal to zero, geometrically this equation, is that of a line not parallel to either axis: we are interested in determining whether it passes through integer points, that is, points with integer numbers as coordinates.
The following proposition gives a necessary and sufficient condition for the equation ax + by = c to admit integer solutions.
Proposition 2.3.0. Equation ax + by = c, a, b, c ∈ ℤ, has an integer solution (x,y), if and only if gcd(a,b) = d divides c.
Proof. Let (x̄, ȳ) be an integer solution of the equation. Then gcd(a,b), dividing a and b, will also be a divisor of the entire left-hand side of the equation and consequently of c. On the other hand, suppose that d divides c. In this case d may be written in the form d = αa + βb. Then, being c = d ⋅ h, we get
c = αha + βhb
and setting (x̄ = ah, ȳ = βh), we find that (x̄, ȳ) is an integer solution of the equation.□
For example the equation
2x + 5y = 3
can be solved in ℤ, becaue (2,5) = 1 divides 3. Then, being 1 = (−2)⋅(2) + (1) ⋅ 5, we get 3 = (−6) ⋅ 2 + (3) ⋅ 5. An integer solution is then (−6,3). Note that this solution is not unique, for example, another integer solution is (9,3).
Corollary 2.3.1. If a| c and b|c, with gcd(a,b) = 1, then ab|c.
Proof. Write c = aq and c = bq' for some integers q and q'. Since gcd(a,b) = 1, there exist x,y ∈ ℤ such that 1 = ax + by. Then c = acx + bcy = a (bq′) x + b (aq) y = ab (q′ x + qy), so ab|c.□
Example 2.3.2. Solve the Diophantine equation 3x − 5y = 0. By the commutative law of multiplication, we have 3 * 5 = 5 * 3. Hence a solution is x = 5 and y = 3. In fact, there are infinitely many solutions as we can multiply this equation by any integer k. From 3⋅(5⋅k) = 5⋅(3⋅k), the general solution is x = 5k and y = 3k. Before we can say that we have solved this equation, we have to show, there are no other solutions. Since 3x = 5y, 3x is divisible by 4. Now (3,5) = 1 hence x is divisible by 5 and therefore x = 5k for k ∈ ℤ, and we have indeed found all the solutions.