1
$\begingroup$

Let $x,y,z \in \mathbb{Z}$. Let $q=gcd(x,y)$. Prove that if $x\nmid zq$ then $x \nmid yz$.

I understand that I can prove this using contrapositive, that is

Let $q=gcd(x,y)$. If $x\mid yz$ then $x \mid zq$.

Assume $x|yz$ and $q = gcd(x,y)$ then $q|x$ and $q|y$.

Then $xk = yz$ for some $k\in \mathbb{Z}$. $qr = x$ for some $r\in \mathbb{Z}$. $qs = y$ for some $s\in \mathbb{Z}$.

By Bezout's Theorum $q = xa + yb$ for some $a,b \in \mathbb{Z}$


I'm not entirely sure how to proceed.

$\endgroup$
  • $\begingroup$ Let $x = x'q$ and $y = y'q$. Then $\gcd(x',y') = 1$. Then $x\not |zq \implies x'q \not |zq \implies x' \not | z \implies x' \not |y'z \implies x'q \not |y'zq \implies x \not |yz$. $\endgroup$ – fleablood Feb 15 '17 at 8:04
1
$\begingroup$

Ignoring the equations involving $r$ and $s$, we have everything we need. Observe that: \begin{align*} q &= xa + yb \\ zq &= xaz + (yz)b \\ zq &= xaz + (xk)b \\ zq &= x \cdot \underbrace{(az + kb)}_{\in ~ \mathbb Z} \end{align*}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.