So here is the statement:
$m \in \mathbb{N} $ and $ a,b \in \mathbb{Z}$. Prove that $\gcd (a,m)=\gcd(b,m)$ iff there are solutions to the linear congruences $ax\equiv b\,(\text{mod}\,\, m)$ and $by\equiv a\,(\text{mod}\,\, m)$.
I tried applying the definition of congruence and rearranging to get $ax-my=b$ and $by-mx=a$ and know that $\gcd(a,m)\big|\,b$ and $\gcd(b,m)\big|\,a$ but I'm stuck from here.
Any help would be appreciated!
On
Hint ($\boldsymbol{\Leftarrow}$): $\gcd(a,m)\mid b$ and $\gcd(a,m)\mid m$ implies $\gcd(a,m)\mid\gcd(b,m)$.
Hint ($\boldsymbol{\Rightarrow}$): Bezout's Identity says that there are $x,u$ so that $ax+mu=\gcd(a,m)$. Furthermore, there is an $s$ so that $s\gcd(b,m)=b$.
On
$\begin{align} \gcd(a,m) = \gcd(b,m) \overset{\rm\ \ Bezout} \iff&\qquad a\Bbb Z\! +\! m\Bbb Z\ \ =\ \ b\Bbb Z\! +\! m\Bbb Z\\ \iff&\ b\in a\Bbb Z\! +\! m\Bbb Z,\ a\in b\Bbb Z\! +\! m\Bbb Z\\ \iff&\ b \equiv ax,\ \ {\rm and}\, \ \ a \equiv by\!\!\pmod m,\ \ {\rm for\ some}\ \ x,y \end{align}$
Remark $\ $ The first equivalence uses the following form of Bezout's Theorem
$$ j\Bbb Z + k \Bbb Z\, =\, \gcd(j,k)\Bbb Z$$
We have:
$$ax \equiv b \pmod m \implies ax + m(-s) = b$$ $$by \equiv a \pmod m \implies by + m(-t) = a$$
From the Bezout's Lemma we have that $(a,m)\mid b$ from the first one and $(b,m)\mid a$ from the second. Now if $(b,m)=p_1p_2...p_k$ then $p_1p_2...p_k \mid m$. From the claim above we have $p_1p_2...p_k \mid a$. Hence $p_1p_2...p_k \mid (a,m) \implies (b,m) \mid (a,m)$. Working other way around we have: $(a,m) \mid (b,m)$. From this we have that $(a,m) = (b,m)$
Now assume that $(a,m) = (b,m)$
Then from Bezout's Lemma $ax + my = d$, has solutions if d is a multiple of $(a,m)$ Hence if we set $d$ as $b$ we have: $(a,m) = (b,m) \mid b$ and the equation has a solution. Prove simularly for the other equation.