Suppose $$d = un + vs$$ where $d$ is the $\gcd(n,s)$

Dividing $d$ both sides

$$1 = u(n/d) + v(s/d)$$

So $(n/d)$ and $(s/d)$ are integers that are relatively prime. Why does this show that for any integer dividing both of them must also divide $1$?

This is a part of a proof I am reading from Abstract Algebra. I like to add that I have limited knowledge in Number Theory

  • 2
    $\begingroup$ If a number divides both n/d and s/d, then that number will divide any multiple of them and their sum, so it will divide 1. $\endgroup$ – anon Mar 4 '13 at 3:51

If $$1 = u(n/d) + v(s/d) := ua + vb,$$ and for some integer $c$ you have $c|a$ and $c|b$, then obviously $$c|ua+vb = 1.$$

Edit (in more detail per a former comment): If $c|a$, then $a = cx$ (not $c = ax$ - example: $2|6$, and $6 = 3 \cdot 2$, not $2 = 3 \cdot 6$). Similarly $b = cy$. Hence, $$ua + vb = ucx + vcy = c (ux + vy),$$ so $c$ divides this. And as only $1|1$, you are done.

  • $\begingroup$ If $c|a$, then $c = ax$ for some integer $x$. Similarly for $b$, that is $c = by$, How does that imply $c | ua + vb$? Because I could have $c | ax + by$ instead no? $\endgroup$ – hosun Mar 4 '13 at 3:50
  • $\begingroup$ I made my comment part of the answer. See above. $\endgroup$ – gnometorule Mar 4 '13 at 3:55

This is (sometimes called) Bezout: $\gcd(a,b)=1$ if and only if there exist $u,v$ such that $au+bv=1$.

You are asking about $\Leftarrow$.

If $n$ divides $a$ and $b$, then $n$ divides $au$ and $bv$, so $n$ divides $au+bv$.

Thus $n$ divides $1=au+bv$.

The only divisors of $1$ are $1$ and $-1$, so $|n|=1$.

Thus $\gcd(a,b)=1$.


$\rm\: m A + n B = 1,\:$ so $\rm\:A\:$ and $\rm\:B\:$ are integers that are relatively prime. Why does this show that for any integer $\rm\,d\,$ dividing both $\rm\,A,B\,$ must also divide $1$?

Hint $\ $ $\rm\:d\mid A,B\:\Rightarrow\: A = ad,\ B\, =\, bd,\ $ so $\rm\ mA \!+ nB \,=\, (ma\!+\!nb)\,d \,=\, 1\:\Rightarrow\:d\mid 1$

Remark $\ $ Since you've tagged it "abstract algebra", a slight abstraction may prove instructive.

More conceptually: if $\rm\ A,B\:$ are multiples of $\rm\:d,\:$ then so too is $\rm\:m A \!+ n B\ \,(=\, 1),\:$ since multiples are closed under both addition and integer scalings $\rm\:x\to nx,\ n\in\Bbb Z,\:$ i.e. they form an ideal in $\,\Bbb Z.\:$ Generally, in any ring, the common multiples of some elements forms an ideal (historically one of the prototypical examples of an ideal). In a principal ideal domain (PID) such as $\rm\,\Bbb Z,\,$ the set of common multiples $\rm\,a,b,\ldots$ is the ideal $\rm\:lcm(a,b,\ldots)\,\Bbb Z.$

Since common multiple sets are ideals, your statement is a special case of the fact that an ideal $\rm\ I = (1)\ $ when it contains two comaximal elements: $\rm\ I\supset (a),(b)\!\iff\! I \supset (a)+(b)\,\ (= 1).\ $ For principal ideals, contains = divides, i.e. $\rm\ (c)\supseteq (a)\!\iff\! c\mid a.\:$ Thus, in a PID, the above specializes to $\rm\:c\mid a,b\!\iff\!c\mid gcd(a,b)\,\ (= 1),\:$ the universal property/definition of the gcd.


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.