Wednesday, August 29, 2018

elementary number theory - Congruence question with divisibility



enter image description here



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

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...