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≡b(modm)⟺a=b+c⋅m where c is some integer
Let aA=bB=k⟹(A,B)=1
⟹k(A−B)=c⋅m
Let (k,m)=D and kK=mM=D⟹(K,M)=1
⟹K⋅D(A−B)=c⋅M⋅D⟺K(A−B)=c⋅M⟹A−B=c⋅MK
As (K,M)=1 and A−B is an integer, K must divide c,
⟹A≡B(modM)⟺ak≡bk(modm(k,m))
as M=mD=m(k,m)
No comments:
Post a Comment