Linear Diophantine equation

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

The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.

Prerequisites

• Integer — Solutions range over integers.
• Greatest common divisor and coprimality — Gcd divisibility is the solvability criterion.
• Linear equation in one variable — The relation is a linear equality.
• 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.