Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

We were given the following problem as an assignment, we proved the converse in class for prime numbers; however, we can't use the assumption that $\operatorname{gcd}(a,b) = 1$. So I am struggling to think of my first possible move.

We are given $ar + bs = 1$, the only think I can think of is let $d$ be a common divisor or $ar + bs$ and then show that the $d = 1$. However, I am not really sure how to do that. If anyone could just give me a hint or two to nudge me in the right direction I would be appreciative.

share|improve this question
Some hint: Try some examples, using Euclidean algorithm. If the algorithm works, then we can determine some integers that work for $ar + bs = 1$. Finally, work out the general case. –  NasuSama Feb 11 at 2:19
add comment

2 Answers

up vote 7 down vote accepted

Hint: Suppose to the contrary that $d\gt 1$ divides both $a$ and $b$. Then $d$ divides $ar$ and $\dots$.

share|improve this answer
add comment

Hint $\ $ Suppose $\,d\mid a,b\,$ is a common divisor of $\,a,b.\,$ From the multiples $\,a,b\,$ of $\,d\,$ we may deduce further multiples of $\,d\,$ because the set of all multiples of $\,d\,$ enjoys a nice algebraic structure: it is closed under the operations of addition and subtraction, since $\,jd\pm kd = (j\pm k) d.\,$. Further, it is closed under multiples $\,m(kd) = (mk)d.\,$ Composing these two operations we deduce that the multiples of $\,d\,$ are closed under arbitrary integer linear combinations, i.e. if $\,a,b\,$ are multiples of $\,d\,$ then so too is $\,ja+kb,\,$ for any integers $\,j,k.$ In your case you happen to know a very small such linear combination which, being a multiple of $\,d,\,$ greatly constrains the possible values of $d.$

Remark $\ $ This algebraic structure of (common) multiples plays a fundamental role in algebra - something that will become much clearer when one learns about ideals and modules.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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