Aquí sólo veremos cómo resolver una ecuación diofántica lineal en dos variables, y lo haremos con un único

Teorema

Supongamos que a y b son enteros no nulos, y d = (a,b)

Si d no divide a c, entonces la ecuación

ax + by = c

no tiene soluciones enteras. Si d divide a c, entonces la ecuación tiene infinitas soluciones, todas de la forma

x = u + tb/d              y = v - ta/d

donde x = u, y = v es una solución cualquiera, y t es un entero.

Demostración:

Como d divide a a y a b, divide también a ax + by con x, y enteros. Por lo tanto, si

ax + by = c          

entonces d divide a c. Si d no divide a c, la ecuación no tiene soluciones enteras.

Supongamos que d divide a c. Entnces existe z entero tal que c = zd

Como d = (a,b), existen r y s enteros tales que

ar + bs =d

por lo que

are + bse = de = c

y la ecuación tiene una solución entera. Si

au + bv = c

entonces

a(u + tb/d) + b(v - ta/d) = au + bv = c

y la ecuación tiene infinitas soluciones.

Sea x, y una solución de la ecuación. Debe cumplirse

a(x - u) + b(y - v) = 0     (E)

(a/d)(x - u) = -(b/d)(y - v)

Entonces (b/d) divide a (a/d)(x - u), pero ((b/d),(a/d)) = 1, por lo que (b/d) divide a x - u, lo que demuestra que existe un entero t tal que

x - u = tb/d

x = u + tb/d

Sustituyendo en (E) se llega a que

y = v - ta/d

con lo que el teorema queda demostrado.