Saturday, June 8, 2019

modular arithmetic - How to compute apmodm1 given that aequivcpmodm2?



Given m1,m2 and we know that
ac(modm1)



Is there a way to directly compute
a(modm2)


Answer



If m2 divides m1 we can. Otherwise we cannot. The reason is that unless m2 divides m1, there will be more than one number x such that 0x<m2 and xc(modm2).



Remark: In connection with your question, we should mention the Chinese Remainder Theorem. If m1 and m2 are relatively prime, then for any d we like, there will be an a such that ac(modm1) and xd(modm2). Thus in the relatively prime case, knowing c gives absolutely no information about the remainder when a is divided by m2.


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...