Linear Diophantine Equations

Number Theory · Axiom Academy

LESSON Linear Diophantine Equations Understanding when integer solutions exist and how to find them The fundamental theorem for linear Diophantine equations tells us exactly when integer solutions exist. In other words, let d = gcd(a, b). Then: If d | c (d divides c), then infinitely many integer solutions exist If d does not divide c, then no integer solutions exist 2. Proof of the Existence Condition Necessity (←): Suppose ax + by = c has a solution (x₀, y₀). Since d = gcd(a, b), we know d | a and d | b. Therefore: This shows that d | c, which is necessary for solutions to exist. Given: d = gcd(a, b) and d | c By Bezout's Identity, there exist integers x₀, y₀ such that: Since d | c, we can write c = kd for some integer k. Multiplying Bezout's equation by k: Therefore, x = kx₀ and y = ky₀ is a solution to ax + by = c. 3. Finding a Particular Solution The Extended Euclidean Algorithm allows us to find a particular solution. The algorithm finds integers x₀ and y₀ such that: Once we have a solution to ax₀ + by₀ = d where d = gcd(a, b), we can scale it to solve ax + by = c. If (x₀, y₀) is one particular solution to ax + by = c, then the general solution is given by: where t is any integer, and d = gcd(a, b). Substituting into the equation: The terms with t cancel because a(b/d) - b(a/d) = 0, leaving ax₀ + by₀ = c. ax + by = c has solutions if and only if gcd(a, b) | c Use the Extended Euclidean Algorithm to find one particular solution Scale the solution when necessary

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