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 ab(modm)a=b+cm where c is some integer



Let aA=bB=k(A,B)=1



k(AB)=cm



Let (k,m)=D and kK=mM=D(K,M)=1




KD(AB)=cMDK(AB)=cMAB=cMK



As (K,M)=1 and AB is an integer, K must divide c,



AB(modM)akbk(modm(k,m))



as M=mD=m(k,m)


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection f:AB and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...