✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · SCI-MAT-002-082

Linear Diophantine Equations

A linear Diophantine equation is an equation of the form ax + by = c, where a, b, and c are integers and the unknowns x and y must also be integers. It has an integer solution if and only if the greatest common divisor of a and b divides c.

ax + by = c has integer solutions ⇔ gcd(a, b) | c

Explanation

Linear Diophantine equations are among the most fundamental equations studied in elementary number theory. Their standard two-variable form is ax + by = c, where a, b, and c are fixed integers and x and y are unknown integers. The central solvability condition is gcd(a, b) | c. If the greatest common divisor of the coefficients does not divide the constant term, no integer solution exists. If it does divide the constant term, infinitely many integer solutions exist, provided a and b are not both zero. The extended Euclidean algorithm can be used to find one particular solution. Once a particular solution (x₀, y₀) is known, all integer solutions can be expressed using a parameter t. If d = gcd(a, b), the general solution is x = x₀ + (b/d)t and y = y₀ − (a/d)t, where t is any integer. This formula describes every integer solution without requiring individual trial-and-error calculations.

Variables

A

The integer coefficient of x.

B

The integer coefficient of y.

C

The integer constant on the right-hand side.

X, y

The unknown integer variables.

D

The greatest common divisor gcd(a, b).

T

An arbitrary integer parameter used to describe all solutions.

X₀, y₀

One particular integer solution.

Example or application

Problem

Solve 6x + 9y = 30 in integers.

Solution

First, gcd(6, 9) = 3, and 3 divides 30, so integer solutions exist. Divide the equation by 3 to obtain 2x + 3y = 10. One particular solution is x₀ = 2 and y₀ = 2, because 2(2) + 3(2) = 10. Since the reduced coefficients are 2 and 3, all solutions are x = 2 + 3t and y = 2 − 2t, where t is any integer.

Answer

x = 2 + 3t, y = 2 − 2t, where t ∈ ℤ.

Text

The greatest common divisor determines whether a linear Diophantine equation is solvable. When a solution exists, the extended Euclidean algorithm provides a systematic way to find one solution, and a parameter formula generates all the remaining integer solutions.

Key Points

  • The standard form is ax + by = c.

  • All coefficients and unknowns are integers.

  • An integer solution exists if and only if gcd(a, b) divides c.

  • If the solvability condition fails, no integer solution exists.

  • If a and b are not both zero and a solution exists, there are infinitely many integer solutions.

  • The extended Euclidean algorithm can produce a particular solution.

  • A parameter formula describes all integer solutions.

Properties

  • If d = gcd(a, b), then d divides every integer combination ax + by.

  • When d divides c, dividing the equation by d produces an equivalent equation with relatively prime coefficients.

  • For a reduced equation with relatively prime coefficients, all solutions differ by integer multiples of the coefficient pair.

  • The general solution contains one free integer parameter.

  • Additional restrictions, such as x > 0 and y > 0, may reduce the infinite solution set to a finite one.

Methods

NameDescription

Greatest Common Divisor Test

Calculate gcd(a, b) and check whether it divides c. This determines whether integer solutions are possible.

Extended Euclidean Algorithm

Find integers u and v satisfying au + bv = gcd(a, b), then multiply by c divided by the greatest common divisor.

General Solution Formula

Use a particular solution and an integer parameter to generate every integer solution.

Applications

  • Solving whole-number allocation problems.

  • Representing a target quantity as a combination of fixed integer quantities.

  • Studying divisibility and linear combinations of integers.

  • Solving problems involving coin denominations and exact totals.

  • Understanding the mathematical basis of modular equations.

Learning Outcomes

  • Recognize a linear Diophantine equation.

  • Apply the greatest common divisor solvability condition.

  • Find a particular integer solution using the extended Euclidean algorithm.

  • Write the general solution of a two-variable linear Diophantine equation.

  • Apply additional restrictions to identify valid solutions.

Practice Questions

  • Determine whether 8x + 12y = 18 has integer solutions.

  • Solve 5x + 7y = 1 in integers.

  • Find all integer solutions of 4x + 6y = 14.

  • Use the extended Euclidean algorithm to solve 15x + 21y = 12.

  • Explain why gcd(a, b) must divide c for ax + by = c to have an integer solution.

  • How do positive-integer restrictions affect the general solution?

Related Concepts

  • Greatest Common Divisor

  • Extended Euclidean Algorithm

  • Bézout's Identity

  • Linear Congruences

  • Integer Solutions and Constraints

Common Mistakes

  • Checking whether a or b individually divides c instead of checking gcd(a, b).

  • Using the Euclidean algorithm without finding the corresponding coefficients.

  • Forgetting to multiply a particular solution by c divided by the greatest common divisor.

  • Giving only one solution instead of the general solution.

  • Using a real parameter instead of restricting the parameter to integers.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • David M. Burton, Elementary Number Theory
  • Kenneth H. Rosen, Elementary Number Theory and Its Applications
  • Titu Andreescu and Dorin Andrica, An Introduction to Diophantine Equations

Suggest a correction or source · More in Arithmetic & Number Theory