Question 1208760: Find an integer x such that when its divided over 5, 7, and 11 gives remainders 2,3, and 10
Answer by math_tutor2020(3817)   (Show Source):
You can put this solution on YOUR website!
Your question is equivalent to solving this system of congruences
x = 2 (mod 5)
x = 3 (mod 7)
x = 10 (mod 11)
We use the Chinese Remainder Theorem to solve this system.
The theorem is applicable because the mod values are pairwise coprime.
GCD(5,7) = 1 and GCD(5,11) = 1 and GCD(7,11) = 1
Each congruence is of the form x = b (mod n)
(b1,b2,b3) = (2,3,10) are the right hand side values
(n1,n2,n3) = (5,7,11) are the modulus values
N = n1*n2*n3 = 5*7*11 = 385
m1 = N/n1 = 385/5 = 77
m2 = N/n2 = 385/7 = 55
m3 = N/n3 = 385/11 = 35
We'll need to find a multiplicative inverse for {m1,m2,m3} with the corresponding mods {n1,n2,n3} in the order presented.
m1 = 77 = 2 (mod 5)
We need to find the multiplicative inverse of 2 mod 5.
We need to solve 2*y1 = 1 (mod 5). Quick trial and error leads to y1 = 3.
m2 = 55 = 6 = -1 (mod 7)
m2*y2 = 1 (mod 7) then solves to y2 = -1 = 6 (mod 7)
m3 = 35 = 2 (mod 11). Solving m3*y3 = 1 (mod 11) leads to y3 = 6 through use of trial and error
Recap so far
(b1,b2,b3) = (2,3,10)
(n1,n2,n3) = (5,7,11)
(m1,m2,m3) = (77,55,35)
(y1,y2,y3) = (3,6,6)
A solution would be
x = y1*b1*m1 + y2*b2*m2 + y3*b3*m3
x = 3*2*77 + 6*3*55 + 6*10*35
x = 3552
The set of all solutions fit the congruence x = 3552 (mod 385)
Recall that N = 385 was the product of the three modulus values.
3552 = 87 (mod 385)
This leads to x = 87 (mod 385)
x = 87 (mod 385) can be translated to the equation x = 385k + 87 where k is an integer.
This describes all possible integer solutions to this system of congruence equations.
There are infinitely many solutions.
A few select solutions are {87, 472, 857, 1242}
--------------------------------------------------------------------------
Answer:
Anything of the form x = 385k + 87 where k is an integer.
Eg: if k = 0 then x = 87 is one solution of infinitely many.
|
|
|
