+0  
 
0
594
4
avatar

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.

 Sep 27, 2017
 #1
avatar
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.

 Sep 27, 2017
 #2
avatar+890 
0

The biggest factor they have in common is 2^2 * 331 = 1324.

 Sep 27, 2017
 #3
avatar
0

It is the common "Modulus" we want, not the biggest common "divisor". That will not satisfy the two equations. Try it!.

 Sep 27, 2017
 #4
avatar+890 
0

Admittedly, the answer is not unique, but

57131 mod 1324 = 199,

37139 mod 1324 = 67.

Try it.

 Sep 27, 2017
edited by Guest  Sep 27, 2017

6 Online Users