If $\gcd(m,n)=1$, and $\gcd(a,m)=\gcd(b,n)=1$, then $\gcd(ab, mn)=1$

943 Views Asked by At

If $\gcd(m,n)=1$, and $\gcd(a,m)=\gcd(b,n)=1$, then $\gcd(ab, mn)=1$.

I tried going about it algebraicallly using the definition of GCD, which gave me $$\left(a u_2+m v_2\right) \left(b u_3+n v_3\right) \left(m u_1+n v_1\right)=1$$ which, when expanded, gives $$a b m u_1 u_2 u_3+a b n u_2 u_3 v_1+a m n u_1 u_2 v_3+a n^2 u_2 v_1 v_3+b m^2 u_1 u_3 v_2+b m n u_3 v_1 v_2+m^2 n u_1 v_2 v_3+m n^2 v_1 v_2 v_3.$$ Unfortunately, factoring with respect to $mn$ and $ab$ does not give me an equation of the form $mnx+aby=1$, as I had hoped.

Then I tried going another route: Assume that $\gcd(ab,mn)=d\neq1$. Then there is a prime $p$. which divides $uab+vmn=d$. Since $p|d$ and $d|mn$ and $d|ab$, $p|mn$ and $p|ab$. Since $p$ is prime, it either divides $m$ or it divides $n$, but since $\gcd(m,n)=1$, it cannot divide both. Without loss of generality, say $p|m$. Since $\gcd(m,a)=1$, $p\not|a$. This means that $p|b$. But I don't know how to get a contradiction from here.

3

There are 3 best solutions below

0
On BEST ANSWER

The statement is not true. Let $m = 3$, $n=4$, $a = 2$, and $b=5$.

Then $\gcd(3,4) = \gcd(2,3) = \gcd(5,4) = 1$, but $\gcd(10,12) = 2$.

0
On

The statement is false, actually.

Let $m=2$, $n=3$, $a=9$, $b=4$. $\gcd(2,3)=\gcd(9,2)=\gcd(4,3)=1$, but $\gcd(9*4,2*3)=\gcd(36,6)=6$

0
On

We're looking for conditions that prevent $ab$ from sharing prime factors with $mn$ - equivalently, for the prime factors of $a, b$ not to be prime factors of $m, n$. In other words, we want each of the $4$ pairs of $a$ or $b$ with $m$ or $n$ to share no prime factors. So the antecedent should really be $$\text{gcd}\left( a,\,m\right) =\text{gcd}\left( a,\,n\right) =\text{gcd}\left( b,\,m\right) =\text{gcd}\left( b,\,n\right) =1.$$ It doesn't matter whether $m,\,n$ have a common factor $>1$.