Proposition 1. If $\def\divides\mathrel{|}u \divides s$ and $v \divides t$ and $\gcd(s,t) = 1$ then $\gcd(u,v) = 1$.

Solution. Assume $u \divides s$ and $v \divides t$. Since $\gcd(u, v) \divides u$, therefore $\gcd(u, v) \divides s$ by (TD). Similarly, $\gcd(u, v) \divides v$, so $\gcd(u, v) \divides t$ as well. Thus, $\gcd(u, v)$ is a common divisor of $s$ and $t$, and hence, assuming $\gcd(s, t) = 1$, we get

$$\gcd(u, v) \le \gcd(s, t) = 1.$$

As $\gcd(u, v)$ is a positive integer that is less than or equal to $1$, then we must conclude that $$\gcd(u, v) = 1.$$

I understand the first part but why does $\gcd(u, v) \le \gcd(s, t) = 1$?

  • $\begingroup$ As $s|t,$ the highest power of any prime that divides $s$ must be $\le$ the highest power of the prime that divides $t$ , right? $\endgroup$ – lab bhattacharjee Dec 6 '13 at 19:20

Assume $u | s$ and $v | t$. Since $gcd(u, v) | u$, therefore $gcd(u, v) | s$ by transitivity of division. Similarly, $gcd(u, v) | v$, so $gcd(u, v) | t$ as well. Thus, $gcd(u, v)$ is a common divisor of s and t ...

Now remember that $gcd(s,t)$ is defined to be the greatest common divisor of $s, t$ i.e. every other common divisor $x$ of $s$ and $t$ will be lower than $gcd(s,t)$ (in fact even $x | gcd(s,t)$ will hold). We just stated that $x=gcd(u,v)$ is a common divisor of $s,t$ which implies $x=gcd(u,v) \le gcd(s,t) = 1$. Thus $gcd(u,v) = 1$.

| cite | improve this answer | |
  • $\begingroup$ Oh I understand. Thanks $\endgroup$ – Kevin Dec 6 '13 at 19:33

Let $s=uk$ and $t=vn$, where $k,n \in \mathbb{Z}$. Then from the condition of the problem and Bezout's Lemma we have that there exist an integers $x,y$ such that:

$$sx + ty = 1$$ $$ukx + vny = 1$$ $$u\underbrace{(kx)}_{r} + v\underbrace{(ny)}_{p} = 1$$ $$ur + vp = 1$$

It's trivial that $r,p \in \mathbb{Z}$. So from Bezout's Lemma this equation has integer solutions $r,p$, so $u$ and $v$ must be comprime number, i.e $gcd(u,v) = 1$

| cite | improve this answer | |
  • $\begingroup$ I can say no reason why one should need Bezout coefficients for this question, I suppose it was just a Pavlov reaction to the symbol $\gcd$. In fact all that goes on is if $g$ is the greatest foo and $f$ is a foo, than $f\leq g$. For foo = "common divisor". $\endgroup$ – Marc van Leeuwen Dec 6 '13 at 20:12
  • $\begingroup$ @MarcvanLeeuwen blue's answer takes another approach, while my approach is little bit different and it's quite simple, right? And as you've said it's maybe a Pavlov reaction, because in years of contest participation, I used Bezout's Lemma for comprime number and it was the first thing that came to my mind after reading the question. $\endgroup$ – Stefan4024 Dec 6 '13 at 20:19
  • $\begingroup$ If you read the question carefully, it is about a literally cited proof that OP has difficulty understanding. That proof clearly does not mention Bezout coefficients, either explicitly or implicitly. So while bringing in those coefficients does lead to a correct proof of the proposition, it does not address OP's question. $\endgroup$ – Marc van Leeuwen Dec 7 '13 at 8:05

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.