I have this question and I have proved that a/d is congruent to b/d mod(m/d)
However, I don't know how to go forward to prove a/k is congruent to b/k mod(m/d)
Can anyone help me out? THX
Answer
We have $a\equiv b\pmod m\iff a=b+c\cdot m$ where $c$ is some integer
Let $\displaystyle \frac aA=\frac bB=k\implies (A,B)=1$
$\implies k(A-B)=c\cdot m$
Let $(k,m)=D$ and $\displaystyle \frac kK=\frac mM=D\implies (K,M)=1$
$\displaystyle\implies K\cdot D(A-B)=c\cdot M\cdot D\iff K(A-B)=c\cdot M\implies A-B=\frac{c\cdot M}K$
As $(K,M)=1$ and $A-B$ is an integer, $K$ must divide $c,$
$\displaystyle\implies A\equiv B\pmod M\iff \frac ak\equiv \frac bk\pmod {\frac m{(k,m)}}$
as $\displaystyle M=\frac mD=\frac m{(k,m)}$
No comments:
Post a Comment