Let $a$ and $m$ be integers such that $m ≥ 1$. Consider the congruence class of $a$, $[a]$ modulo $m$. It follows that $∀ x ∈ [a], \gcd(x, m) = \gcd(a, m)$.
I have my algebra midterm in two days! In my lecturer's note, it was stated the above statement and I have no idea why is it true? I asked my lecturer, but he didn't want to answer, instead asked me to prove it. I have no idea where to start. Any help would be highly appreciated.
If $x \in [a]_m$ then you have $x=a+km$ for some $k$ (or $a = x-km$)
Then if $d \mid a$ and $ d \mid m$, you must have $d \mid x$.
Similarly, if $d \mid x$ and $ d \mid m$, you must have $d \mid a$.
Hence the set of divisors of the pair $a,m$ is the same as the set of divisors of $x,m$ hence the greatest divisors must be the same.
Note: The essential result here is that if you have $c = ax + by$ and you also have $d \mid a$ and $d \mid b$, then you must have $d \mid c$. This follows by writing $a=a_1 d, b=b_1 d$ hence $c = (a_1x+b_1y) d$.