This question already has an answer here:
- Why $\gcd(qb+r,b)=\gcd(b,r)$? 8 answers
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.