$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$?
Why is $a$ and $b$ coprime if $a\equiv 1 \pmod{b}$?
3 Answers
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$?
-
0@did: Yes. Brandon cited what I commented was not necessarily unique. It was my mistake. Sorry. – 2012-07-08
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)$
-
0No fair! :-) (+1) – 2012-06-17
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