Linear Diophantine equation: ax + by = c has integer solutions iff gcd(a,b)|c. Extended Euclidean algorithm: find x₀,y₀ such that ax₀ + by₀ = gcd(a,b). Scale to get particular solution. General: x = x₀(c/d) + (b/d)t, y = y₀(c/d) − (a/d)t.
How to Use
Enter coefficients:
- a, b, c: Integer coefficients
- gcd: Solvability check
- Solution: x, y parameterized by t
Algorithm
Extended Euclidean: gcd(a,b) = ax₀+by₀. If d=gcd(a,b) divides c, multiply by c/d. General solution adds multiples of (b/d, −a/d) to the particular solution.
Applications
- Coin problems (Chicken McNugget)
- Cryptography (RSA key generation)
- Number theory proofs
- Integer programming
Step-by-Step Instructions
- 1Enter a, b, c.
- 2Check if gcd(a,b)|c.
- 3Get particular solution.
- 4View general solution.
- 5Find specific solutions.