What is the smallest positive integer that will satisfy the following four modular equations:
N mod 427 = 277
N mod 1,427 = 1,125
N mod 11,527 = 4,739
N mod 111,727 =105,788
Thank you for help.
Can somebody help me with this please? Heureka, Gingerale, Melody, anybody? Thanks.
I shall give you an accurate answer, even though some people don't like it, because there are "formal methods" of solving such modular equations, using "Euler's totient function" and "Chinese Remainder Theorem" and other formal methods etc.
The method I use, which is considered "ineffcient!!" is a simple heuritic method of trial and error basically, and finds the answer very quickly. It begins by taking the largest modulus, 111,727 in this case, and searches all numbers beginning with 1 as follows: it starts with 1 X 111,727 + 105,788=217,515. Then it takes this number and tests it on the 2nd modular equation by subtracting the remainder of 4,739 and dividing by its modulus of 11,527 and see if it divides it EVENLY. It it does, then it has found the answer. If it doesn't, then it tries 2, 3, 4, 5......etc. until it finds the A, B, C, D. This is perfectly acceptable in the Math World, but is considered "inefficient", especially when the numbers get to be very large.
So, based on the above explanation, here is my solution to your modular equations and good luck to you !!.
A * 427 + 277=B *1,427 + 1,125 =C * 11,527 + 4,739=D * 111,727 + 105,788. Using simple iteration, we have:
A = 2,602, B = 778, C= 96, D = 9. Therefore:
N=[2,602 x 427] + 277 =1,111,331- smallest positive integer.
Since the LCM of {427, 1,427, 11,527, 111,727}=112,105,840,448,063, therefore:
N=112,105,840,448,063n + 1,111,331, where n=0, 1, 2, 3.....etc.
