Sign in to watch this lesson
Advanced - Number Theory · 3:54
Linear Diophantine Equations
The equation a·x + b·y = c has integer solutions exactly when g = gcd(a, b) divides c, and one solution comes from extended Euclid scaled by c/g. All solutions lie evenly spaced on a line, x = x0 + k·b/g and y = y0 − k·a/g, so counting them inside limits means intersecting two ranges of k with floor division, and any linear cost is optimal at an end of that range.
You will learn
- Decide whether a·x + b·y = c has integer solutions (g | c) and build one from extended Euclid, including negative coefficients and a = b = 0
- Write every solution as x = x0 + k·b/g, y = y0 − k·a/g and explain why there are no others
- Count solutions inside x and y limits in O(1) after extended Euclid, using floor division rather than C++ truncation
- Minimise a linear cost over the solutions by checking the ends of the allowed k-range