Greatest Common Divisor multiplicative proof

99 Views Asked by At

Given : gcd(m,n) = 1 , gcd(d1,d2) = 1.
Show : gcd(m,d1)*gcd(n,d2) = gcd(mn,d1d2).

Is my proof for above correct ?
If no , what have I missed ?
If yes , is there any better way to prove it ?

Proof :

pi , qi , ei , fi are prime numbers.

m = p1k1p2k2....psks...pwkw
d1 = p1a1p2a2....psas es+1bs+1 ...exax
n = q1l1q2l2....qtlt qt+1bt+1 ...qyly
d2 = q1g1q2g2....qtgt ft+1gt+1 ...fzgz

gcd(m,d1) = p1min(k1,a1)p2min(k2,a2)...psmin(ks,as)
gcd(n,d2) = q1min(l1,g1)q2min(l2,g2)...qtmin(lt,gt)
mn = p1k1p2k2....psks...pwkwq1l1q2l2....qtlt qt+1bt+1 ...qyly
d1d2 = p1a1p2a2....psas es+1bs+1 ...exaxq1g1q2g2....qtgt ft+1gt+1 ...fzgz
gcd(mn , d1d2) = q1min(l1,g1)q2min(l2,g2)...qtmin(lt,gt)p1min(k1,a1)p2min(k2,a2)...psmin(ks,as)

gcd(mn , d1d2) = gcd(m, d1)*gcd(n, d2)

Please do confirm if it is correct.

Sorry for the title , not appropriate.

1

There are 1 best solutions below

3
On

The claim is false so your proof cannot be correct, e.g. put $\, m> 1\,$ below

$$\begin{align} (m,d_1)(n,d_2) &= (m\cdot n,\, d_1\cdot d_2)\\[.3em] 1 = (m,1)\,(1,m)\, &\neq (m\cdot 1,\,1\cdot m) = m\end{align}\qquad$$

To debug your proof put $\,m=2\,$ above and find the first line in your proof that fails for these values.

Remark $\ $ Generally if $\, (m,n) = 1 = (d_1,d_2)\,$ then we have

$$(mn,d_1 d_2) = (m,d_1 d_2) (n,d_1d_2) = (m,d_1)\color{#c00}{(m,d_2) (n,d_1)}(n,d_2)\qquad $$

and the latter $= (m,d_1) (n,d_2) \iff \color{#c00}{(m,d_2) = 1 = (n,d_1)}$