Generalization of Division by GCD

302 Views Asked by At

Let $x,y,z \in \mathbb{Z}$ where $x \neq 0$ or $y \neq 0$. If $z$ is a common divisor and $z \neq 0$, prove $$ gcd(x,y) / |z| = gcd(x/z, y/z)$$


I realize this can be written as $$ gcd( x/|z|, y / |z|) = gcd(x/z, y/z) $$ But I am unsure as to how to continue as $ |z| \neq z$ .

1

There are 1 best solutions below

0
On BEST ANSWER

To see this, use Bezout's theorem. Let $g = \gcd(x,y)$. Then, there exist integers $a,b$ such that $g = ax+by$.

Since $|z|$ divides $g$, we have that $g/|z| = a(x/|z|) + b(y/|z|)$.

The above shows that $\gcd(x/|z|, y/|z|) \leq g/|z|$.

However, the other way is also true: suppose that $h = \gcd(x/|z|, y/|z|)$, then there exist integers $a,b$ such that $h = a(x/|z|) + b(y/|z|)$. Multiplying by $|z|$, we get that $h|z| = ax + by$. Therefore, we see that $h|z| \geq g$, by Bezout's theorem.

Combining these, $h=g$.