# 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

-
You do know that in general, $C$ and $c$ are considered different things, right? – Arturo Magidin Feb 23 '11 at 4:18
What you write in the title is silly. $a$ is always congruent to $b$ modulo $\gcd(a,b)$, because they both leave remainder $0$ when divided by their greatest common divisor. $c$, $r$, and $s$ are completely irrelevant. Methinks you miscopied. – Arturo Magidin Feb 23 '11 at 4:20
You probably means $a$ congruent to $b$ modulo $\gcd(r,s)$, didn't you? – Arturo Magidin Feb 23 '11 at 4:26

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$?

-

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

-

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

-