# Linear Diophantine equation

This English edition is an AI candidate and does not yet have an OCME Atlas (GPT-6) Twin closure receipt.

A nondegenerate integer equation a*x+b*y=c has a solution exactly when gcd(a,b) divides c; all solutions have one integer parameter.

mko-linear-diophantine-equation · definition · v0.10.0



## Mathematical statement

Use an extended Euclidean Bezout certificate for a particular solution. If d=gcd(a,b) divides c, all solutions are x=x0+(b/d)t and y=y0−(a/d)t, t∈Z. When a=b=0, c=0 permits every integer pair and c≠0 permits none; never divide by d=0.





## Representative formula (exact TeX)

a(x)+b(y)=c





## Assumptions


- a,b,c are exact integers, retaining signs and individual zero coefficients.
- The full parameterization uses the canonical Euclidean construction rather than a bounded search.





## Symbol scope


- t — integer solution parameter
- d — nonnegative gcd





## Intuition, definition, and misconceptions

Gcd divisibility is necessary and sufficient in the nondegenerate case.

One solution is not all solutions; step sizes must use the normalized gcd.

Double-zero coefficients form an independent degenerate branch.

Finding one pair does not list all integer solutions, and double-zero coefficients must not divide by gcd0.





## Adopted derivation guide

[All integer solutions with a negative coefficient](https://ocme.evemisslab.com/en/derivations/derivation-mko-linear-diophantine-equation-01/)The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.





## Prerequisites


- [Integer](https://ocme.evemisslab.com/en/mko/mko-integer/) — Solutions range over integers.
- [Greatest common divisor and coprimality](https://ocme.evemisslab.com/en/mko/mko-gcd-coprime/) — Gcd divisibility is the solvability criterion.
- [Linear equation in one variable](https://ocme.evemisslab.com/en/mko/mko-linear-equation/) — The relation is a linear equality.
- [Euclidean algorithm](https://ocme.evemisslab.com/en/mko/mko-euclidean-algorithm/) — Bezout witnesses construct the parameterization.





## Verification boundary

Only two-variable linear integer equations are handled; higher-dimensional lattices and nonlinear Diophantine problems are separate.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.





## Next obligation

Add multi-variable integer linear systems and Smith normal form.





## Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.

[Canonical MKO JSON](https://ocme.evemisslab.com/data/mko/linear-diophantine-equation.json) · [Plain Markdown](https://ocme.evemisslab.com/en/mko/mko-linear-diophantine-equation/index.md)