# If u|s and v|t and gcd(s,t) = 1 then gcd(u,v) = 1

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

• 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? – 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$.

• Oh I understand. Thanks – 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$

• 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". – Marc van Leeuwen Dec 6 '13 at 20:12
• @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. – Stefan4024 Dec 6 '13 at 20:19
• 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. – Marc van Leeuwen Dec 7 '13 at 8:05