# Let d = gcd(a, b), prove kd = gcd(ka, kb)

1. Apr 7, 2012

### youvecaughtme

I feel like I am convoluting this problem. Any help is appreciated! Also, I'm not sure how to rewrite the first part to make it more readable. Any help here is appreciated, too.

1. The problem statement, all variables and given/known data
Let a and b be integers and let d = gcd(a, b). If k is a positive integer, prove that
kd = gcd(ka, kb).

HINT: Set d1 = gcd(ka, kb). Argue that kd is a common divisor of ka and kb, so kd
divides d1 . Next, apply Theorem 5 to argue that d1 divides kd.

2. Relevant theorems
Theorem 4: Let a and b be integers and suppose d = gcd(a, b). Then there exist integers
m and n such that d = ma + nb.

Theorem 5: Let a, and b be integers, where a and b are not both zero. Then gcd(a, b)
exists so let d = gcd(a, b). For an integer c there exist integers m and n such that
c = ma + nb if and only if c is a multiple of d.

3. The attempt at a solution
Proof. Let $a, b, d \in \mathbb{Z}$ such that $d=\mathrm{gcd}(a,b)$. Let $k$ be a positive integer and set $d_1=\mathrm{gcd}(ka, kb)=kma+knb \implies d_1=k(ma+nb)$. Because $d|a$ and $d|b$, $d_1=kd(\frac{ma}{d}+\frac{nb}{d})$. Therefore, $kd|d_1$. Using Theorem 5, because $kd$ divides $d_1$, $d_1$ is a multiple of $d$ and therefore $d_1=ra+sb$

From here, I'm not sure where to go. I don't know how to introduce k back into $d_1=ra+bs$