Congratulations, you have solved it.
You have used the fact that $\gcd(a+b,b)=\gcd(a,b)$

We give a proof of the type you were writing, but with the logical details made more explicit.

Theorem: (Bézout's Identity) Two integers $m$ and $n$ are relatively prime **if and only if** there exist integers $s$ and $t$ such that $ms+nt=1$.

Because $a$ and $b$ are relatively prime, there exist integers $x$ and $y$ such that $ax+by=1$.

Since $d\mid a$, there is an integer $k$ such that $a=dk$.

It follows that $d(kx)+by=1$. Thus (taking $s=kx$ and $t=y$) we conclude that $d$ and $b$ are relatively prime.

The second problem is more awkward if we want to use linear combinations, but it can be done that way. Since $a$ and $b$ are reatively prime, we have $ax+by=1$ for some integers $x$ and $y$.

Now consider linear combinations $as+ct$ of $a$ and $c$. We have $acx+bcy=c$, and therefore
$$as+ct=as+(acx+bcy)t=a(s+cxt)+bc(yt).$$
Thus any linear combination of $a$ and $c$ is a linear combination of $a$ and $bc$.

The converse is obvious: any linear combination of $a$ and $bc$ is a linear combination of $a$ and $c$.

It follows that the set of linear combinations of $a$ and $c$ is **the same** as the set of linear combinations of $a$ and $bc$. Thus in each case the smallest positive linear combinations are the same, and hence the gcd's are the same.

## Best Answer

Let $d=\gcd(a,n)$, let $a=da'$, and let $n=db$. Then $ab=(da')b=a'(db)=a'n$.

So $ab$ is a multiple of $n$, but $1\le b\lt n$.

That takes care of showing that if $a$ and $n$ are not relatively prime, then there is an appropriate $b$.

To show that when $a$ and $n$ are

notrelatively prime, there is no such $b$, suppose $[a][b]=[0]$. So $n$ divides $ab$. Since $a$ and $n$ are relatively prime, the by a theorem you probably already know, we have that $n$ divides $b$.