Diophantine equations are equations where the solutions must be integers, such as whole numbers or negative whole numbers. They are named after Diophantus of Alexandria and appear throughout number theory, cryptography, puzzles, and computer science. The restriction to integers makes familiar algebra much more selective because many real-number solutions no longer count.
A central example is the linear Diophantine equation ax + by = c, where a, b, and c are integers and we search for integer pairs (x, y).
The key idea for ax + by = c is divisibility by the greatest common divisor of a and b. Integer solutions exist exactly when gcd(a, b) divides c. Once one solution is found, all solutions can be generated by stepping through a regular pattern on the integer lattice.
This makes Diophantine equations a powerful bridge between algebra, divisibility, and geometric patterns on grids.
Key Facts
- A Diophantine equation is an equation whose solutions are restricted to integers.
- A linear Diophantine equation in two variables has the form ax + by = c, where a, b, and c are integers.
- The equation ax + by = c has integer solutions if and only if gcd(a, b) divides c.
- If d = gcd(a, b) and d divides c, divide by d to simplify: (a/d)x + (b/d)y = c/d.
- If (x0, y0) is one solution to ax + by = c, then all solutions are x = x0 + (b/d)t and y = y0 - (a/d)t, where t is any integer and d = gcd(a, b).
- The Euclidean algorithm can find gcd(a, b), and the extended Euclidean algorithm can find one integer solution.
Vocabulary
- Diophantine equation
- An equation for which only integer solutions are allowed.
- Integer solution
- A solution in which every variable is an integer, such as -3, 0, or 8.
- Greatest common divisor
- The greatest common divisor, or gcd, of two integers is the largest positive integer that divides both of them.
- Linear Diophantine equation
- A Diophantine equation where the variables appear only to the first power, such as ax + by = c.
- Integer lattice
- The integer lattice is the grid of points in the coordinate plane whose coordinates are both integers.
Common Mistakes to Avoid
- Forgetting to check gcd(a, b) divides c: this is wrong because ax + by = c has no integer solutions unless the greatest common divisor of a and b divides c.
- Treating any real-number solution as valid: this is wrong because Diophantine equations require integer values for the variables.
- Finding one solution and stopping: this is incomplete because a linear Diophantine equation usually has infinitely many integer solutions that follow a formula.
- Using the wrong signs in the general solution: this is wrong because if x increases by b/d, then y must decrease by a/d to keep ax + by equal to c.
Practice Questions
- 1 Determine whether 18x + 30y = 42 has integer solutions. If it does, find one solution.
- 2 Find the general integer solution to 7x + 5y = 1.
- 3 Explain why the points that solve ax + by = c form a straight line, but only some points on that line count as Diophantine solutions.