Mathwords logoMathwords

Diophantine Equation — Definition, Formula & Examples

A Diophantine equation is a polynomial equation where you are only looking for integer solutions. Named after the ancient Greek mathematician Diophantus, these equations often have no solution, finitely many, or infinitely many integer solutions.

A Diophantine equation is an equation of the form f(x1,x2,…,xn)=0f(x_1, x_2, \ldots, x_n) = 0, where ff is a polynomial with integer coefficients and the unknowns x1,x2,…,xnx_1, x_2, \ldots, x_n are restricted to Z\mathbb{Z}. A solution is any nn-tuple of integers satisfying the equation.

Key Formula

ax+by=chas integer solutions  ⟺  gcd⁡(a,b)∣cax + by = c \quad \text{has integer solutions} \iff \gcd(a, b) \mid c
Where:
  • a,ba, b = Integer coefficients
  • x,yx, y = Integer unknowns
  • cc = Integer constant on the right-hand side
  • gcd⁡(a,b)\gcd(a,b) = Greatest common divisor of a and b

How It Works

To solve a linear Diophantine equation ax+by=cax + by = c, first compute d=gcd⁡(a,b)d = \gcd(a, b). The equation has integer solutions if and only if d∣cd \mid c. If a particular solution (x0,y0)(x_0, y_0) exists, the general solution is x=x0+bd tx = x_0 + \frac{b}{d}\,t and y=y0−ad ty = y_0 - \frac{a}{d}\,t for any integer tt. For nonlinear Diophantine equations, techniques vary widely — modular arithmetic, descent arguments, and algebraic number theory are all commonly used.

Worked Example

Problem: Find all integer solutions to 6x + 9y = 21.
Check solvability: Compute gcd(6, 9) = 3. Since 3 divides 21, integer solutions exist.
gcd⁡(6,9)=3,3∣21  ✓\gcd(6, 9) = 3, \quad 3 \mid 21 \; \checkmark
Simplify: Divide the entire equation by 3 to get an equivalent equation.
2x+3y=72x + 3y = 7
Find one solution: By inspection, x₀ = 2 and y₀ = 1 works since 2(2) + 3(1) = 7.
x0=2,y0=1x_0 = 2, \quad y_0 = 1
Write the general solution: Using the general solution formula with a = 2, b = 3, d = 1:
x=2+3t,y=1−2t,t∈Zx = 2 + 3t, \quad y = 1 - 2t, \quad t \in \mathbb{Z}
Answer: All integer solutions are (x,y)=(2+3t,  1−2t)(x, y) = (2 + 3t,\; 1 - 2t) for any integer tt. For example: (2,1)(2, 1), (5,−1)(5, -1), (−1,3)(-1, 3), etc.

Why It Matters

Diophantine equations appear throughout number theory and cryptography — RSA encryption relies on properties of integer factorization closely tied to these equations. Fermat's Last Theorem, one of the most famous results in mathematics, states that xn+yn=znx^n + y^n = z^n has no positive integer solutions for n≥3n \geq 3, making it a statement about a specific Diophantine equation.

Common Mistakes

Mistake: Assuming integer solutions always exist for any right-hand side.
Correction: The linear equation ax + by = c has integer solutions only when gcd(a, b) divides c. For example, 6x + 9y = 10 has no integer solutions because gcd(6, 9) = 3 does not divide 10.