GCD proofs

**Maccaman** · March 22nd 2009, 06:17 AM

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?

**Grandad** · March 22nd 2009, 09:45 AM

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$

Grandad

Thread: GCD proofs

LinkBack

Thread Tools

Display

GCD proofs

GCD

Similar Math Help Forum Discussions

proofs

lim sup and lim inf proofs

More Proofs

Proofs

Sequence Convergence Proofs vs. Continuity Function Proofs

Search Tags