Show that if $a$ is an odd en integer and $b$ is an even integer then $\gcd(a,b)=\gcd(a,b/2)$.
I understand that since $a$ is not divisible by $2$ but $b$ is, the gcd of $a$ and $b$ also can't be divisible by $2$ but I'm getting stuck using this to help me.
Best Answer
We will show that (i) If $k$ divides $a$ and $b/2$, then $k$ divides $a$ and $b$ and (ii) If $k$ divides $a$ and $b$, then $k$ divides $a$ and $b/2$.
This will sow that the set of common divisors of $a$ and $b$ is the same as the set of common divisors of $a$ and $b/2$. Since the sets are the same, the maximum elements of the sets (the gcds) are the same.
Proof of (i): We need only show that $k$ divides $b$. We have $\frac{b}{2}=kq$ for some integer $q$, and therefore $b=k(2q)$, so $k$ divides $b$.
Proof of (ii): We need to show that $k$ divides $\frac{b}{2}$. Let $\frac{b}{2}=b^\ast$. Then $b=2b^\ast$.
Because $k$ divides $a$, and $a$ is odd, it follows that $k$ is odd. So the odd integer $k$ divides $2b^\ast$. But $k$ and $2$ are relatively prime, so $k$ divides $b^\ast$.