Finding All Solutions

Number Theory · Axiom Academy

LESSON Finding All Solutions to Linear Diophantine Equations Master the general solution formula and learn to find all integer solutions to ax + by = c 1. The General Solution Formula If we know one particular solution (x₀, y₀) to the equation ax + by = c where gcd(a,b) = d, then ALL integer solutions are given by the parametric equations: where t ∈ ℤ is any integer parameter. Each value of t generates a different solution! Let's understand why this formula generates all solutions. Suppose (x₀, y₀) and (x₁, y₁) are both solutions to ax + by = c. Since gcd(a/d, b/d) = 1, this means (a/d) divides (y₁ - y₀) and (b/d) divides (x₁ - x₀). Therefore: 3. Understanding the Parametric Form The parametric equations describe a line in the integer lattice ℤ². Each integer value of t gives us a lattice point on this line. t = -2: x = -5, y = 5 → Check: 6(-5) + 9(5) = -30 + 45 = 15 t = -1: x = -2, y = 3 → Check: 6(-2) + 9(3) = -12 + 27 = 15 t = 0: x = 1, y = 1 → Check: 6(1) + 9(1) = 6 + 9 = 15 t = 1: x = 4, y = -1 → Check: 6(4) + 9(-1) = 24 - 9 = 15 4. Finding Solutions in a Specific Range Often we need to find solutions where both x and y are positive (or in some other range). We set up inequalities for the parameter t. 5. Counting Solutions in a Range To count how many solutions exist in a given range, we find the range of valid t values and count the integers in that interval. 6. Real-World Applications: Coin and Stamp Problems

This is the written version of the interactive lesson above. See the full Number Theory course.