State/Solutions to homogeneous linear Diophantine equations can be found with the LCM

Logical Connections

This statement logically relies on the following definitions and statements: Def/Least common multiple, Def/Bijection

The following statements and definitions rely on the material of this page: Def/Domain topograph

To visualize the logical connections between this statements and other items of mathematical knowledge, you can visit the following cluster(s), and click the "Visualize" tab: Clust/Basic number theory

The following SAGE code demonstrates the connection between linear Diophantine equations and the LCM. It has been adapted from a SAGE worksheet created by Erik Jacobson.

In the following code snippets, try several values for $a$ and $b$ until you see the relationship between $LCM(a,b)$ and the family of solutions to the equation $ax + by = 0$.

First, define $a$ and $b$, let $\ell = LCM(a,b)$, and consider the vector $(\ell/a, \ell/b)$.

a = 28
b = 12
l = lcm(a,b)
l/a, l/b

Now, consider the Diophantine equation $ax + by = 0$. Given $x$, one may find a unique $y$ satisfying this equation, by the formula $y = -ax / b$.

With the following code, you can list all solutions $(x,y)$, with $x$ an integer between $-10$ and $10$, and $y$ a rational number.

for x in range(-10,10):
        print "When x =",x,", y = ",-a*x/b,"."

Looking at the output, when are both $x$ and $y$ integers? What does this have to do with the vector $(\ell / a, \ell / b)$ that was found earlier?