# 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
$\displaystyle gcd(x, yz) > 1$ $\displaystyle \Rightarrow \exists$ a prime $\displaystyle p$ such that $\displaystyle p|x$ and $\displaystyle p |yz$

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

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

$\displaystyle \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

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

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

$\displaystyle 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 $\displaystyle (a,b) = k$ and $\displaystyle c \mid a$ and $\displaystyle c \mid b$, then $\displaystyle c \mid k \qquad {\color{red}\star}$

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

___________

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

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

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

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

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

But $\displaystyle (x,z) = 1$. Can you conclude?

7. ## Divisors and multiples

Originally Posted by o_O
• If $\displaystyle (a,b) = k$ and $\displaystyle c \mid a$ and $\displaystyle c \mid b$, then $\displaystyle 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.