Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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$?

share|cite|improve this answer

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

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.