# [SOLVED] gcd proof 1

• Feb 17th 2009, 06: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, 09:02 AM
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

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

• Feb 17th 2009, 09:05 AM
maths900
Thanks. Is there another way to proof this-without having a contradiction or or something?
• Feb 17th 2009, 09:23 AM
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

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

• Feb 17th 2009, 09: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

$\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.
• Feb 17th 2009, 10:29 AM
o_O
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?
• Feb 17th 2009, 12:23 PM
Divisors and multiples
Quote:

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.