# How to prove that if $(ab,n)=1$ then, $(r,n)=1$? [duplicate]

This question already has an answer here:

Let $$ab=nq+r$$ where all variables represent integers with $$0\leq r. 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 StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); 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.

• 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$". – астон вілла олоф мэллбэрг Mar 25 at 6:58
• Hint: use [Bezout's lemma] (proofwiki.org/wiki/B%C3%A9zout%27s_Lemma) – Mostafa Ayaz Mar 25 at 8:10
• $1 = (ab,n) = (nq+r,n) = (r,n)\,$ by the linked dupe. – Bill Dubuque Mar 25 at 14:33

## 1 Answer

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