# Thread: [SOLVED] gcd proof 1

1. ## [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

2. ## GCD

Hello maths900
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$

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

3. Thanks. Is there another way to proof this-without having a contradiction or or something?

4. ## GCD

Hello maths900
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$

5. 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$

Yes that is the way i had started it but i couldnt end the proof.

6. 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?

7. ## Divisors and multiples

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.