Exercise 0.2.4 (General solution of $ax + by = N$)

Question

Let $a, b$ and $N$ be fixed integers with $a$ and $b$ nonzero and let $d = (a,b)$ be the greatest common divisor of $a$ and $b$. Suppose $x_0$ and $y_0$ are particular solutions to $ax + by = N$ (i.e., $ax_0 + by_0 = N$). Prove for any integer $t$ that the integers
$$x = x_0 + \frac{b}{d} t,\qquad 	ext{and}\qquad y=y_0 - \frac{a}{d} t$$
are also solutions to $ax + by = N$ (this is in fact the general solution).

Richard Ganaye · Accepted Answer

\begin{proof} 
Let $a\wedge b = d$ denote the $\mathrm{g.c.d}$ odf $a,b$.

We verify that $x= x_0 + \frac{b}{d} t$ and $y=y_0 - \frac{a}{d} t$ are solutions for any integer $t$:
\begin{align*}
ax +by &= a \left(x_0 + \frac{b}{d} tight) + b \left( y_0 - \frac{a}{d} tight)\
&= ax_0 + by_0 + \frac{ab}{d} t -  \frac{ab}{d} t\
&= ax_0 + by_0\
&= N.
\end{align*}
Conversely, let $(x,y)$ be any solution of $ax +by = N$. Then $a x + by = a x_0 + by_0$, so $a(x -x_0) = -b (y-y_0)$, and since $d\mid a$ and $d \mid b$,
\begin{align}
A(x- x_0) = -B (y-y_0),\qquad 	ext{where} \qquad A = \frac{a}{d} \in \mathbb{Z},\ B = \frac{b}{d}\in \mathbb{Z}.
\end{align}
Then $B \mid A (x-x_0)$, where $A \wedge B = \frac{a}{d} \wedge \frac{b}{d} = \frac{a\wedge b}{d} = 1$. Therefore $B \mid x-x_0$, so there is some $t \in \mathbb{Z}$ such that $x = x_0 = t B$. If we substitute $x- x_0$ by $tB$ in (1), we obtain $t AB = -B(y-y_0)$, where $B 
e 0$ (since $n 
e 0$ by hypothesis), thus $y-y_0 = -tA$. This gives
\begin{align}
x = x_0 + \frac{b}{d} t,\qquad y=y_0 - \frac{a}{d}.
\end{align}
So (2) is the general solution of $ax +by = N$ (where $(x_0, y_0)$ is a particular solution).
\end{proof}

Exercise 0.2.4 (General solution of $ax + by = N$)

Answers

Comments

Exercise 0.2.4 (General solution of $ax + by = N$)

Answers

Comments

Add answer