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
If $c\equiv a \pmod{r}$ and $c\equiv b\pmod{s}$, prove $a\equiv b\pmod{\gcd(a,b)}$
-
1You probably means $a$ congruent to $b$ modulo $\gcd(r,s)$, didn't you? – 2011-02-23
3 Answers
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)$