0
$\begingroup$

I'm working on the following question:

Suppose that $a,b \in \mathbb{Z}$ and are not both $0$. Suppose also that $g = \gcd(a,b)$. Show that $d$ is a common divisor of $a$ and $b$ if and only if $d \mid g$.

$\Longrightarrow$

Since $\gcd (a,b) = g$, we can say that $g \mid a$ and $g \mid b$. By Bezout's theorem, $\exists x,y \in \mathbb{Z}$ such that

$$ax+by = g.$$

(That's as far as I got)

$\Longleftarrow$

I need to show that $g \mid a$ and $g \mid b$ so that $d$ can be a common divisor of $a$ and $b$.

Any suggestions as to where I should go next would be much appreciated.

$\endgroup$
1
$\begingroup$

$\implies$ If $d$ is a common divisor of $a$ and $b$ then $\exists i,j\in \mathbb{Z}$ s.t. $a=id$ and $b=jd$. So by Bezout's identity $\exists x,y \in \mathbb{Z}$ s.t. $$ax+by=idx+jdy=d(ix+jy)=g$$ and so $d|g$

$\Longleftarrow$ Assume $d|g$. By definition $g|b$ and $g|a$, and by transitivity of divisibility, $d$ divides both $a$ and $b$.

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