What is the smallest number which leaves remainder 4 , 7 and 9 respectively when divided by 5, 8 and 10 but there is no remainder if it divided by 7.
Answers
Brute Force: Create sets of all multiples of all numbers satisfying the conditions pick the solution i.e. First set is {2,9,16,23, ....} second set is { 4,12, 20, 28 ...} and third set is {6,15,24,33,42, ....} once you have done you will find the answer to be 492
Algebraic approach:
N = 2+ 7m = 4+8n = 6+ 9p, Now, take first two equations implying (2+7m) mod 8 = 4; and 7m mod 8 should be 2. Giving us 7m = 42 and a new equation: 56q + 42 (remainder here is a multiple of 7 giving remainder 2 and 56= lcm (7,8) ); gives N = 44 + 56 q satisfying both equations
Similarly use third equation (6+9p) with this new equation (44 + 56q) makes (44+56q) mod 9 should be 6 gives (44 mod 9 + a multiple of 56 giving remainder 7 and lcm (56 ,9) = 504) = 492 + 504 r
Chinese Remainder Theorem (works smoothly if the given numbers are co-prime otherwise the solution requires some changes to the numbers)
Lets us call the three remainders 2, 4 and 6 r1, r2 and r3 respectively and the numbers 7, 8 and 9 as n1, n2 and n3 respectively
Calculate N = n1 * n2 * n3 = 504 (numbers are co-prime i.e. LCM = product of numbers)
N1 = N/ n1 = 72; N2 = N/n2 = 63; N3 = N/n3 = 56
y1 is defined as a number when N1 * y1 mod (n1) = 1; hence (72 * y1) mod 7 = 1 gives y1 = 4
y2 == for N2 * y2 mod (n2) = 1 gives y2 = 7
y3 == for N3 * y3 mod (n3) = 1 gives y3 = 5
Calculate M = r1 * N1 * y1 + r2 * N2 * y2 + r3 * N3 * y3 = 4020
M mod (N) is the solution = 4020 mod 504 = 492