 Solution

The condition $\gcd (a,b,n)=1$ says that the ideal of $\mathbb{Z}$ generated by $a,b,n$ is all of $\mathbb{Z}$. The multi-integer Bezout identity therefore supplies integers $r,s,t$ such thatEquivalently, first apply Bézout's identity to $a,b$ and then to $\gcd (a,b),n$.