Solve Linear Indeterminate Equation
Intermediate

Video tutorial

Lecture Notes

A linear equation $ax + by = c$ is solvable if and only if $c$ is a multiple of the greatest common divisor of $a$ and $b$. In particular, if $a$ and $b$ are co-prime, then $ax + by = 1$ is always solvable. Conversely, if $ax +by=1$ is solvable, then $a$ and $b$ are co-prime (Bezout's Theorem).

When a linear equation is solvable, then it will have an infinite number of solutions. Assume $(x_0, y_0)$ is any of these solutions, then all the solutions can be written in the following form where $t$ is an integer parameter: $$\left\{\begin{align}x = x_0 +bt\\ \\ y=y_0-at\end{align}\right.$$

In addition to the trial-and-error method (which is suitable for simple problems), the Euclidean method can be used to find one solution to a linear equation.

Alternatively, it is also possible to solve a linear equation (especially those having more than two variables) using the elimination method.