# Why is $a$ and $b$ coprime if $a\equiv 1 \pmod{b}$?

$a$ and $b$ are coprime if their greatest common divisor is 1. How do I conclude that from the fact that $b$ divides $a-1$?

If $b\mid a-1$, then there is an integer $n$ such that $a-1=bn$, and therefore $a-bn=1$. Suppose that $d\mid a$ and $d\mid b$: then $d\mid a-bn$. (Why? If you’re in any doubt, you should write out the details of the argument.) What does that tell you about $d$?

• @Babak: As a note, $p$ and $q$ are not unique. $d = a(p+kb) + b(q-ka)$ for any $k \in \Bbb Z$. – Brandon Carter Jul 4 '12 at 4:37
• @Babak And this remark is not needed to complete Brian's answer, which is already complete. – Did Jul 8 '12 at 7:42
• @did: Yes. Brandon cited what I commented was not necessarily unique. It was my mistake. Sorry. – mrs Jul 8 '12 at 7:52

Hint $\begin{eqnarray}\qquad \rm mod\!\!\!\! &\rm\,\ \ \color{#C00}b\!:&\rm\ \color{#C00}{ a}\ |\ c \\ \Rightarrow\, &\rm\! (\color{#C00}b\,\! &\!\!\!\!,\ \rm\color{#C00} a)\,|\:c\ \ in\ \ \mathbb Z \end{eqnarray}\ \ \bigg\}$ $\begin{eqnarray} &&\rm{\bf Proof}\quad\! m\:\!b+n\,a\, =\, c\ \ \,so\,\ \ (b,a)\:|\:b,a\:\Rightarrow\:(b,a)\:|\:c\\ &&\rm{\bf Note}\quad\ \ c=1\,\ \ yields\ your\ special\ case. \end{eqnarray}$

Remark $\$ The converse is true too, as follows from Bezout, viz. $$\rm (b,a)\:|\:c \iff b\,\mathbb Z + a\,\mathbb Z\,\ni\, c\iff a\:|\:c\ \ (mod\ b)$$

• No fair! :-) (+1) – robjohn Jun 17 '12 at 17:39

If a≡1(mod b), there exists an integer k such that a=1+b.k

(a,b)=(1+b.k,b)=(1+b.k-b.k, b) as (a,b)=(a-b.m,a) for any integer m.

=>(a,b)=(1,b)=1