1. ## GCD proofs

Hi There,
I really don't like Number theory, and i'm terrible with it. Can someone please show me how to prove the following?
$gcd(ac,bd) >= gcd(a,b) * gcd(c,d)$ for all a,b,c,d which are natural numbers.

Also, Is $gcd(ac,bd) = gcd(a,b) * gcd(c,d)$ for all a,b,c,d which are natural numbers? Why?

2. ## GCD

Hello Maccaman
Originally Posted by Maccaman
Hi There,
I really don't like Number theory, and i'm terrible with it. Can someone please show me how to prove the following?
$gcd(ac,bd) >= gcd(a,b) * gcd(c,d)$ for all a,b,c,d which are natural numbers.
Let $\gcd(a,b) = p, \gcd(c,d) = q$.

Then $\exists\, s,t,u,v \in \mathbb{N},a = ps, b=pt, c = qu, d=qv$

$\Rightarrow ac = pqsu, bd=pqtv$

$\Rightarrow pq$ is a common factor of $ac$ and $bd$

$\Rightarrow \gcd(ac, bd) \ge pq = \gcd(a,b)\cdot\gcd(c,d)$

Also, Is $gcd(ac,bd) = gcd(a,b) * gcd(c,d)$ for all a,b,c,d which are natural numbers? Why?
No; whenever (for $p, q, s,t,u,v$ defined as above) $\gcd(s, v) > 1$ or $\gcd(t,u) > 1, \gcd(ac, bd) > pq$.

E.g. $a = 4, b = 6, c = 5, d = 10 \Rightarrow \gcd(a,b) = 2, \gcd(c,d) = 5$, but $\gcd(ac,bd) = \gcd(20,60) = 20 \ne 2\times 5$