4
$\begingroup$

Here is what I got so far:

Let $\gcd(ka,km) = d$

Then by the Euclidean Algorithm, we have integers $s,t$ such that:

$$s(ka) + t(km) = d \implies k|d $$

Let $$d/k = g = sa + tm. \tag{1}$$

So now I need to show that $g$ is indeed = $\gcd(a,m)$. Let $\gcd(a,m) = h$

Now since $k|d \implies d|a , d|m \space $ (since $$\gcd(ka,km) = d \implies g| \gcd(a,m) = h \\\implies h = dj ,$$ for some integer $j$.

Putting this into (1):

$$ h/jk = g = sa + tm $$

since $$h = dj \implies dj/j = kg \\ \implies d = kg. $$

So $g$ is the $\gcd(a,m)$?

Is this a correct proof? Or have I gone in some sort of circle? Many thanks for any hints or direction!

$\endgroup$
  • 1
    $\begingroup$ Looking at your proof it seems you have the logical steps correct in your mind but while typing here you have made lot of mistakes. For example $k\mid d$ implies that $g = d/k$ divides $a, m$ and not $d \mid a, d \mid m$. If you correct this part then you should get $h = gj$. Next you should try to establish $g = hi$ for some integer $i$. This will give $d/k = g = h$. $\endgroup$ – Paramanand Singh Aug 28 '13 at 9:04
  • $\begingroup$ You can get $g = hi$ in following way. Clearly $h$ divides $a, m$ so that $a = hl, m = hn$ so that $ g = sa + tm = shl + thn = h(sl + tn) = hi$. $\endgroup$ – Paramanand Singh Aug 28 '13 at 9:10
1
$\begingroup$

You seem to be on the right track, although I'm not so sure about your last step. Also, I would avoid using fractions when possible. Here's my approach.

Let $g = \gcd(a,m)$ and let $d = \gcd(ka,km)$. We want to show that $d = kg$.

Since $d = \gcd(ka,km)$, we know by the Extended Euclidean Algorithm that $d = (ka)s + (km)t$ for some $s,t \in \Bbb Z$. But then observe that $d = k(as + mt)$. Hence, it suffices to prove that $g = as + mt$.

Since $g = \gcd(a,m)$, we know by the Extended Euclidean Algorithm that $g$ is the smallest possible integer that can be expressed in the form $ax + my$, where $x,y \in \Bbb Z$. But since $as + mt$ can also be expressed in this form, we know that $\boxed{g \leq as + mt}$.

Since $g=ax+my$, we may scale this equation by $k$ to obtain $kg = (ka)x + (km)y$. But recall that $d$ is the smallest possible integer that can be expressed in the form $(ka)s + (km)t$, where $s,t \in \Bbb Z$. Hence, we have $k(as + mt)=d \leq kg$ so that cancelling the $k$ from both sides yields the inequality $\boxed{as + mt \leq g}$ (we assume, without loss of generality, that $k\geq0$).

Finally, since $g \leq as + mt$ and $as + mt \leq g$, we have shown that $g=as+mt$, as desired.

$\endgroup$
1
$\begingroup$

This is proven using Bezout's Identity in this answer.

Bezout says that $$ \gcd(a,b)=\inf\{ax+by\gt0:x,y\in\mathbb{Z}\} $$ Then we simply note that $$ \inf\{cax+cby\gt0:x,y\in\mathbb{Z}\} $$ is both $c\gcd(a,b)$ and $\gcd(ac,bc)$.

I believe this is very similar to your proof, but I think you need to exploit the fact that $\gcd(a,b)$ is the smallest positive $ax+by$ for any $x,y\in\mathbb{Z}$.

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