I have this math problem.

Let $a, b, m$ be any positive integers with $\gcd(a,m)=d$ and $\gcd(b,m)=1$.

i) Show that if $k$ is a common divisor to $ab$ and $m$, then $k$ divides $d$.

ii) Use the result in part i) to conclude that $\gcd(ab, m)=d$.

I'm not 100% sure about how to start this. Can I conclude that if $k\mid ab$, then $k\mid a$? If I can do that, then I can say since $k\mid a$ and $k\mid m$, $k\mid d$.



Yes, you can make that conclusion. The best way to check the validity of a claim like that is writing down a more detailed proof like below:

Let $k$ be a common divisor to $ab$ and $m$. Since $k|m$ and $(b,m) = 1$, $(b,k) = 1$. Thus $k|ab$ and $(b,k) = 1$ implies $k |a$, and thus also $k|d$.

For part (ii), $k|d$ implies $k \leq d$. Since $k|m$ and $k|ab$, $gcd(ab,m) \leq d$. But since $d |ab$ and $d|m$, we know $gcd(ab,m) \geq d$. Thus $gcd(ab, m) = d$.


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.