If $a \equiv b \pmod m $ and $ a \equiv c \pmod n$, Prove that $b \equiv c \pmod d$ where $d=\gcd(m,n)$
We have $a-b=km$ where $k$ is an integer And $a-c=ln$ where $l$ is an integer Now $b-c=ln-km$ What I need to do after this
Asked
Active
Viewed 132 times
1
-
What is MN?.... – Phira Jun 22 '18 at 18:02
-
1This is false as stated. $1\equiv 3\pmod 2$ and $1\equiv 6\pmod 5$ but $3\not \equiv 6\pmod {10}$. – lulu Jun 22 '18 at 18:02
-
But how to get that? – John757 Jun 22 '18 at 18:04
-
How to get what? The statement you want to prove is simply not true. Perhaps you typed it incorrectly? Or left off some important assumptions? – lulu Jun 22 '18 at 18:05
-
I typed it wrong – John757 Jun 22 '18 at 18:06
-
Ok...so, correct it. As far as I can see, the recent edit didn't change anything. My counterexample still holds. – lulu Jun 22 '18 at 18:09
-
@lulu is it correct now – John757 Jun 22 '18 at 18:15
-
Yes! This version makes sense. Write $m=dM,n=dN$ and we see that $a-b=kdM,a-c=ldN$ Subtract to see that $b-c=ldN-kdM$ and remark that $d$ divides the right hand. – lulu Jun 22 '18 at 18:18
2 Answers
0
$a\equiv b\pmod m \implies a= b + pm\\ a\equiv c\pmod n \implies a= c + qn$
Setting $a= a$ gives us $b + pm = c + qn$
$b \equiv c \pmod d$ if $d|pm$ and $d|qn$
Doug M
- 57,877
0
$$(a-b=km)\wedge (b-c=\ell n)\implies a-c=km+\ell n.$$ Now by definition, the ideal $\:\bigl\{km+\ell n\mid k,\ell\in\mathbf Z\bigr\}\:$ is the ideal generated by $d=\gcd(m,n)$. Thus $a-c\in d\mathbf Z$.
Bernard
- 175,478