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

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

  • $\begingroup$ No fair! :-) (+1) $\endgroup$ – 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.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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