This question already has an answer here:

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.


marked as duplicate by Bill Dubuque divisibility Mar 25 at 14:30

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 2
    $\begingroup$ What you have written , starting from "If $d = (r,n)$" and ending with "Therefore $(r,n) = 1$" is an acceptable rigorous mathematical proof! You have figured out how to frame the equations, and the explanation is also correct. Once again I repeat, your argument is fine. "Reasoning it out verbally" would be something like : "Any divisor of $r$ and $n$ is by the given equation a divisor of $ab$ and $n$ and hence a divisor of $1$, hence equal to $1$". $\endgroup$ – астон вілла олоф мэллбэрг Mar 25 at 6:58
  • $\begingroup$ Hint: use [Bezout's lemma] (proofwiki.org/wiki/B%C3%A9zout%27s_Lemma) $\endgroup$ – Mostafa Ayaz Mar 25 at 8:10
  • $\begingroup$ $1 = (ab,n) = (nq+r,n) = (r,n)\,$ by the linked dupe. $\endgroup$ – Bill Dubuque Mar 25 at 14:33

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.$$


Not the answer you're looking for? Browse other questions tagged or ask your own question.