If gcd$(a,b) = 1$, then I want to prove that $\forall c \in \mathbb{Z}$, $ax + by = c$ has a solution in integers $x$ and $y$.

If gcd$(a,b) = 1$, then I want to prove that $\forall c \in \mathbb{Z}$, $ax + by = c$ has a solution in integers $x$ and $y$.

This is what I was attempting or trying:

Let $d =$ gcd$(a,b)$.

$d|a \Rightarrow \exists k \in \mathbb{Z}$ s.t. $a = dk$.

$d|b \Rightarrow \exists l \in \mathbb{Z}$ s.t. $b = dl$

Substituting these in we get $dkx + dly = c \Rightarrow d(kx + ly) = c \Rightarrow d|c$ and $(kx+ly)|c$.

I'm not sure if this proves it or not. The help would be appreciated!

Solution 1:

You have proved that if $d\mid a$ and $d\mid b$, and $c=ax+by$, then $d\mid c$. That is not at all what we want to show.

The result will be easy once we prove:

Lemma: If $\gcd(a,b)=1$, there exist integers $s$ and $t$ such that $as+bt=1$.

Taking the Lemma for granted temporarily, note that if $as+bt=1$ then $a(cs)+b(ct)=c$, so we can take $x=cs$ and $y=ct$ to prove our result. But the hard part is

Proof of Lemma: We sketch the standard proof. Let $K$ be the set of all positive integers that can be represented in the form $au+bv$, where $u$ and $v$ range over the integers. The set $K$ is non-empty, so has a smallest positive element $k$. So there is a $u_1,v_1$ such that $k=au_1+bv_1$. We show that $k=1$. That will complete the proof.

Suppose to the contrary that $k\gt 1$. The number $k$ cannot divide both of $a$ and $b$, for if it did we would violate $\gcd(a,b)=1$. Without loss of generality we may assume $k$ does not divide $a$. Then $a=qk+r$, for some integers $q$ and $r$ such that $0\lt r\lt k$.

But then $$r=a-qk=a-q(au_1+bv_1)=a(1-qu_1)+b(-qv_1).$$ Since $0\lt r\lt k$, this contradicts the fact that $k$ is the smallest positive integer of the shape $au+bv$.

Solution 2:

since $(a,b)=1$ we can find integers $p,q$ so that the $2 \times 2$ matrix: $$ M = \begin{pmatrix}a & b \\ p & q \end{pmatrix} $$ has determinant $1$. let $d$ be an arbitrary integer, and consider the equation: $$ \begin{pmatrix}a & b \\ p & q \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix}c \\ d \end{pmatrix} $$ this has solution $$ \begin{pmatrix} x \\ y \end{pmatrix} =\begin{pmatrix}q & -b \\ -p & a \end{pmatrix} \begin{pmatrix}c \\ d \end{pmatrix} $$ i.e. $$ x = qc-bd \\ y = ad - pc \\ $$ you may verify that, whatever the value of $d$, we have: $$ ax + by = aqc - abd +bad -bpc = (aq-bp)c = |M|c = c $$