If $c\equiv a \pmod{r}$ and $c\equiv b\pmod{s}$,  prove $a\equiv b\pmod{\gcd(a,b)}$ I ran into this problem with my abstract algebra homework the other night, and I think I am really close to solving it.  By the definition of modulo n, I know that
c=a + rm, m being some integer
c=b + sn, n being some integer
I want to prove a=b + (rm + sn)
I have tried algebraically manipulating these equalities, but to no avail.  Is this the right track, or do I need a different approach?  I have a quiz tomorrow, so an answer would be much appreciated. :D 
 A: I am guessing that the question you are trying to ask is:

If $c$ is congruent to $a$ modulo $r$, and $c$ is congruent to $b$ modulo $s$, then $a$ is congruent to $b$ modulo $\gcd(r,s)$ (not modulo $\gcd(a,b)$).

If so: you know $r$ divides $c-a$, so $\gcd(r,s)$, which divides $r$, also divides $c-a$. And $s$ divides $c-b$, so $\gcd(r,s)$ divides $c-b$. So $\gcd(r,s)$ divides both $c-a$ and $c-b$, which means it divides their difference. Which just happens to be...
Or along what you write: express $r$ and $s$ as multiples of $\gcd(r,s)=d$. Since $r=dk$ and $s=d\ell$ for some $k$ and $\ell$, you get
\begin{align*}
c &= a+rm = a+d(km).\\
c &= b+sn = b+d(\ell n).
\end{align*}
That means $a+d(km) = b+d(\ell n)$. Now, can you write $a = b+dt$ for some integer $t$?
A: Suppose $c \equiv a \pmod r$ and $c \equiv b \pmod s$. We want to show that $a \equiv b \pmod{t}$ where $t = \gcd(r,s)$. So $c-a = rl$ and $c-b = sm$ for $l,m \in \mathbb{Z}$. So $a-b = sm-rl$. 
A: HINT $\rm\ \ \ d\ |\ r\ |\ c-a,\ \ \ d\ |\ s\ |\ c-b\ \ \Rightarrow\ \ d\ | \ c-b-(c-a)\ =\ a-b\:.\ $ Now put $\rm\ d = gcd(r,s)$
