If a = b (mod m) and gcd(a,b) = 1, then gcd(a,m) = 1

Question

I can't figure out how to prove this. I know m | (a-b) and I know that there is some integers x and y such that ax + by = 1, however I do not know how to connect these two things to prove the result that the gcd(a,m) = 1. Please help!

Answer 1

Given the assumptions, we can write $b=a+mk$ and $ax+by=1$ for some $k,x,y\in\Bbb Z$. Hence, $$ax+(a+mk)y=1\implies a(x+y)+m(ky)=1$$

Answer 2

(Following the comments on the OP)

We want to show that any $d$ that divides both $a$ and $m$ must divide $1$.

We know that $b=a+km$. Therefore, if $d|a$ and $d|m$, then also we have $d|b$. But, if $d$ divides both $a$ and $b$, then it divides $(a,b)$, which is $1$.