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$.

Question

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!

Answer 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$.

Answer 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 $$

Answer 3

Another way: $ $ by Euler $\phi$, $\,\ \begin{align}(a,b)=1\\ n= \phi(b)\ \end{align} $ $\, \Rightarrow\ \begin{align} c\,&\equiv\, a^{\large n}c\!\pmod{\! b}\\ {\rm i.e.}\,\ \ c\,&=\, a (a^{\large n-1}c)+b\,y \end{align}$

Remark $\ $ See here for alternative proofs. What works best in any given context depends on the order that the basic theorems are presented. There are many possible orders, e.g. see Pierre Samuel's Sur l'organisation d'un cours d'arithmétique, L'Enseignement Mathématique, 13 (1967) 223-231, where he examines in detail approaches based on all possible permutations of a few fundamental theorems (one uses Lagrange's theorem to derive the gcd Bezout equation, as here).

Update $\ $ The linked answer's thread has been deleted so I repost the answer below.

---

Hint $\ $ Use Euler's Theorem $\rm \,(c,m)=1\,\Rightarrow\,c^{\large \phi(m)}\equiv 1\pmod m,\,$ or use Bezout as follows:

$$\rm \exists\, x\in\Bbb Z\!:\ cx\equiv b\!\!\!\pmod{\! m}\!\iff\! \exists\, x,y\in\Bbb Z\!:\ cx\!+\!my = b\!\overset{\rm\ Bezout}\iff\!\gcd(c,m)\mid b$$

Or use the following

Theorem $\ $ The following are equivalent for integers $\rm\:c,\, m.$

$(1)\rm\ \ \ gcd(c,m) = 1$
$(2)\rm\ \ \ c\:$ is invertible $\rm\,(mod\ m)$
$(3)\rm\ \ \ x\to cx+d\:$ is $\:1$-$1\:$ $\rm\,(mod\ m)$
$(4)\rm\ \ \ x\to cx+d\:$ is onto $\rm\,(mod\ m)$

Proof $\ (1\Rightarrow 2)\ $ By Bezout $\rm\, gcd(c,m)\! =\! 1\Rightarrow cd\!+\!km =\! 1\,$ for $\rm\,d,k\in\Bbb Z\,$ $\rm\Rightarrow cd\equiv 1\!\pmod{\! m}$
$(2\Rightarrow 3)\ \ \ \rm cx\!+\!d \equiv cy\!+\!d\,\Rightarrow\,c(x\!-\!y)\equiv 0\,\Rightarrow\,x\!-\!y\equiv 0\,$ by multiplying by $\rm\,c^{-1}$
$(3\Rightarrow 4)\ \ $ Every $1$-$1$ function on a finite set is onto (pigeonhole).
$(4\Rightarrow 1)\ \ \ \rm x\to cx\,$ is onto, so $\rm\,cd\equiv 1,\,$ some $\rm\,d,\,$ i.e. $\rm\, cd+km = 1,\,$ some $\rm\,k,\,$ so $\rm\gcd(c,m)=1$

See here for a conceptual proof of said Bezout identity for the gcd.