Prove that, given $a,b,d$ integers, if $d$ is a common divisor of $a$ and $b$, then $\frac{\gcd(a,b)}{d}=\gcd(\frac{a}{d},\frac{b}{d})$.
So far I have what was given:
$a=dk$, $b=dk'$
Now: i give the $\gcd$ the next value $\gcd(a,b)=t$ and so i know that
- $t$ divides $a$ then $a=t*t'$
- $t$ divides $b$ then $b=t*t''$
- $d$ divides $t$ then $t=rd$
- $t$ can be expressed as the linear combination $t=ax +by$
That is all the information that I have.
I don't know how to start. I tried to start by
$\frac{\gcd(a,b)}{d}=\frac{t}{d}=\dots$ but I keep getting nowhere.
How should I proceed?
Best Answer
We know that there exist $x,y \in \mathbb{Z}$ s.t.
$$\gcd(a,b) = ax + by$$
Now divide both sides by $d$ to get that:
$$\frac{\gcd(a,b)}{d} = \frac ad x + \frac bd y$$
From here we conclude that $\gcd\left(\frac ad, \frac bd\right)$ divides $ \frac{\gcd(a,b)}{d}$
Similarly we have that there exist $s,t \in \mathbb{Z}$ s.t
$$\gcd\left(\frac ad, \frac bd\right) = \frac ad s + \frac bd t$$
Multiply both sides by $d$ to get that
$$d \cdot\gcd\left(\frac ad, \frac bd\right) = a s + b t$$
From here we get that $\gcd(a,b)$ divides $d \cdot\gcd\left(\frac ad, \frac bd\right)$
From both relation we conclude that $\gcd\left(\frac ad, \frac bd\right)= \frac{\gcd(a,b)}{d}$. Hence the proof.