4
$\begingroup$

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

3 Answers 3

7

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
3

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

  • 0
    No fair! :-) (+1)2012-06-17
0

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