# [SOLVED] gcd proof 1

Printable View

• Feb 17th 2009, 07:57 AM
maths900
[SOLVED] gcd proof 1
Show that if g.c.d.(x,y) = g.c.d.(x,z) = 1 then g.c.d.(x,yz) = 1
• Feb 17th 2009, 10:02 AM
Grandad
GCD
Hello maths900
Quote:

Originally Posted by maths900
Show that if g.c.d.(x,y) = g.c.d.(x,z) = 1 then g.c.d.(x,yz) = 1

$gcd(x, yz) > 1$ $\Rightarrow \exists$ a prime $p$ such that $p|x$ and $p |yz$

$\Rightarrow p |y$ or $p| z$

$\Rightarrow gcd(x, y) = p$ or $gcd(x,z) = p$

Contradiction.

$\Rightarrow gcd(x, yz) = 1$

Grandad
• Feb 17th 2009, 10:05 AM
maths900
Thanks. Is there another way to proof this-without having a contradiction or or something?
• Feb 17th 2009, 10:23 AM
Grandad
GCD
Hello maths900
Quote:

Originally Posted by maths900
Thanks. Is there another way to proof this-without having a contradiction or or something?

Why should you want to? This is a standard mathematical technique.

If you want to try to prove it directly, you could perhaps start by saying

$gcd(x, y) = 1 \Rightarrow \exists m,n \in \mathbb{Z}, mx + ny = 1$

Grandad
• Feb 17th 2009, 10:25 AM
maths900
Quote:

Originally Posted by Grandad
Hello maths900Why should you want to? This is a standard mathematical technique.

If you want to try to prove it directly, you could perhaps start by saying

$gcd(x, y) = 1 \Rightarrow \exists m,n \in \mathbb{Z}, mx + ny = 1$

Grandad

Yes that is the way i had started it but i couldnt end the proof.
• Feb 17th 2009, 11:29 AM
o_O
One important fact:
• If $(a,b) = k$ and $c \mid a$ and $c \mid b$, then $c \mid k \qquad {\color{red}\star}$

Basically, any common divisor of two numbers will divide the gcd of those two numbers.

___________

Let $d = (x,yz) \geq 1$.

$(x,y) = 1 \ \Leftrightarrow \ mx + ny = 1$

Multiply both sides by $z$: $mxz + nyz = z$

Since $d \mid x(mz)$ and $d \mid yz(n)$, then $d \mid z$. (Why?)

But this means $d \mid x$ and $d\mid z$ which implies $d \mid (x,z)$ because of ${\color{red}\star}$.

But $(x,z) = 1$. Can you conclude?
• Feb 17th 2009, 01:23 PM
Grandad
Divisors and multiples
Quote:

Originally Posted by o_O
• If $(a,b) = k$ and $c \mid a$ and $c \mid b$, then $c \mid k \qquad {\color{red}\star}$

Basically, any common
multiple of two numbers will divide the gcd of those two numbers.

The proof is fine, but I think you mean divisor here.

Grandad

• Feb 17th 2009, 01:30 PM
o_O
Whoops! Yes, that's what I meant.