What is the Modulus that will satisfy the following two equations?

57,131 mod N =199 and 37,139 mod N =67. Thanks for any help.

Guest Sep 27, 2017

#1**0 **

We don't have a direct method of finding the Modulus, but we can proceed as follows:

If the Modulus =M

If the quotient =Q for the first and =q for the second, then we have:

MQ + 199 = 57,131.................(1), and:

Mq + 67 =37,139...................(2)

Will ignore the Modulus "M" for now and re-write the two equations as:

Q =57,131 - 199 =56,932.........(3)

q =37,139 - 67 =37,072.........(4). Will factor (3) and (4) as follows:

56,932 = 2^2 * 43 * 331, and:

37,072 = 2^4 * 7 * 331

From the above factorization, we can readily see that the biggest factor they have in common is =331. Then we have:

57,131 mod 331 = 199, and

37,139 mod 331 = 67. And that satisfies both equations.

Guest Sep 27, 2017