+0  
 
0
232
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.

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

Guest Sep 27, 2017
 #2
avatar+889 
0

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

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

Guest Sep 27, 2017
 #4
avatar+889 
0

Admittedly, the answer is not unique, but

57131 mod 1324 = 199,

37139 mod 1324 = 67.

Try it.

Bertie  Sep 27, 2017
edited by Guest  Sep 27, 2017

18 Online Users

New Privacy Policy

We use cookies to personalise content and advertisements and to analyse access to our website. Furthermore, our partners for online advertising receive information about your use of our website.
For more information: our cookie policy and privacy policy.