gcd - general solution

[logistic_guy]

Let \(\displaystyle a, b\) and \(\displaystyle N\) be fixed integers with \(\displaystyle a\) and \(\displaystyle b\) nonzero and let \(\displaystyle d = (a,b)\) be the greatest common divisor of \(\displaystyle a\) and \(\displaystyle b\). Suppose \(\displaystyle x_0\) and \(\displaystyle y_0\) are particular solutions to \(\displaystyle ax + by = N \ (\text{i}.\text{e}., ax_0 + by_0 = N)\). Prove for any integer \(\displaystyle t\) that the integers

\(\displaystyle x = x_0 + \frac{b}{d}t \ \ \ \) and \(\displaystyle \ \ \ y = y_0 - \frac{a}{d}t\)

are also solutions to \(\displaystyle ax + by = N \ \) (this is in fact the general solution).

 

[logistic_guy]

We have:

\(\displaystyle ax + by = N \ \)

Let us try to substitute.

\(\displaystyle a\left(x_0 + \frac{b}{d}t\right) + b\left(y_0 - \frac{a}{d}t\right) = N \ \)

Simplify.

\(\displaystyle ax_0 + a\frac{b}{d}t + by_0 - b\frac{a}{d}t = N \ \)


\(\displaystyle ax_0 + by_0 = N \ \)

Then,

the integers \(\displaystyle x\) and \(\displaystyle y\) are also solutions.