Saturday, 25 October 2025

Exercise (1.4).14

Prove the following result:

Let $\gcd (a, b) = 1$ and a positive integer $k$ divides $c$. Let $x_0, y_0$ be particular solutions of the equation $$akx + bky= c$$

Then all the other solutions of this equation are given by

$$x = x_0 + (\frac{b}{k})t \quad \text{and} \quad y= y_0− (\frac{a}{k})t$$

where $t$ is any integer.


Using Proposition 1.18, the general solution to the equation $akx + bky= c$, given a particular solution $x_0, y_0$, is

$$x = x_0 + (\frac{bk}{g})t \quad \text{and} \quad y= y_0− (\frac{ak}{g})t$$

where $t$ is any integer, and $g=\gcd(ak,bk)$.


Let's focus on $g$

$$\begin{align} g &= \gcd(ak, bk) \\ \\ & =  k \gcd(a,b) \quad \text{Proposition 1.11} \\ \\ & = k (1) \quad \text{given } \gcd(a,b)=1 \\ \\ &= k \end{align}$$


So the general solution is

$$x = x_0 + bt \quad \text{and} \quad y= y_0− at$$

where $t$ is any integer.


Note: this is not what the exercise says the general solution is, and I believe there is a typo in the textbook.