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.

  • $\begingroup$ pls. correct the title $\endgroup$ – G Cab Apr 7 '16 at 17:11
  • $\begingroup$ What is wrong? Can you be specific? $\endgroup$ – Shoutre Apr 7 '16 at 17:13

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


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.