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

Printable View

- Feb 17th 2009, 06:57 AMmaths900[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 AMGrandadGCD
Hello maths900$\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$

Contradiction.

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

Grandad - Feb 17th 2009, 09:05 AMmaths900
Thanks. Is there another way to proof this-without having a contradiction or or something?

- Feb 17th 2009, 09:23 AMGrandadGCD
- Feb 17th 2009, 09:25 AMmaths900
- Feb 17th 2009, 10:29 AMo_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 PMGrandadDivisors and multiples
- Feb 17th 2009, 12:30 PMo_O
Whoops! Yes, that's what I meant.