Let $ab=nq+r$ where all variables represent integers with $0\leq r<n$. If $(ab,n)=1$ then how to prove that $(r,n)=1$? I need to prove this to help me understand the proof of Euler's theorem better.
I have been able to reason it out verbally but I want to prove it rigorously using equations. If $d=(r,n)$ then $d|r$ and $d|n$. Therefore $d|(nq+r)$. Therefore $d|ab$. But $(ab,n)=1$. Since $d|n$ and $d|ab$, hence $d=1$. Therefore $(r,n)=1$. I cannot figure out how to frame the equations to express this. Please help.
By Bezout $$uab+vn=1$$ for somme $u,v\in \mathbb Z$. Then $$unq+ru+nv=1\implies ru+n(uq+v)=1\implies (r,n)=1.$$