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)}$
1
$\begingroup$
elementary-number-theory
-
1You do know that in general, $C$ and $c$ are considered different things, right? – 2011-02-23
-
2What 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. – 2011-02-23
-
1You probably means $a$ congruent to $b$ modulo $\gcd(r,s)$, didn't you? – 2011-02-23