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?
$\displaystyle gcd(ac,bd) >= gcd(a,b) * gcd(c,d)$ for all a,b,c,d which are natural numbers.

Also, Is $\displaystyle 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?
$\displaystyle gcd(ac,bd) >= gcd(a,b) * gcd(c,d)$ for all a,b,c,d which are natural numbers.
Let $\displaystyle \gcd(a,b) = p, \gcd(c,d) = q$.

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

$\displaystyle \Rightarrow ac = pqsu, bd=pqtv$

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

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

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

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