I'm trying to prove something about divisilibity and got stuck for long hours in the following:
All the integers mentioned below are $\geq 0$.
Let $q$ and $m$ be integers and let $d$ be a divisor of $m$.
Show that if $q<d$ and $\operatorname{gcd}(q,d)=1$, then $\operatorname{gcd}(q\cdot\frac{m}{d},m)=\frac{m}{d}$.
My attempt:
Well, clearly $\frac{m}{d}$ divides both. Suppose that there is a $k>\frac{m}{d}$ such that $k$ divides both.
I'm trying to conclude then that $k$ must divide $\frac{m}{d}$, but the fact that $\frac{m}{d}$ and $q$ are not necessarily coprime is making things really difficult. By doing some examples and seeing what was going on, I came up with the formula \begin{equation} m-q\cdot\frac{m}{d}=\frac{m}{d}(d-q), \end{equation} which gives the question for $q=d-1$.
How can I finish this proof? Thanks.
I find this route simpler:
Since $\gcd(q,d)=1$, there are $x,y \in \mathbb Z$ such that $qx+dy=1$.
Multiplying both sides by $\dfrac md$,we get $ q\dfrac md x +my = \dfrac md $.
This proves that $\dfrac md$ is a multiple of $\gcd(q\dfrac md,m)$.
Since $\dfrac md$ is a common divisor of $q\dfrac md$ and $m$, it must divide $\gcd(q\dfrac md,m)$.
Therefore, $\dfrac md=\gcd(q\dfrac md,m)$.