What is the smallest positive integer that will satisfy the follwing congruences:x mod 17 =1, x mod 7 = 2, x mod 31 = 3 and x mod 23 =4. Thank you for help.
x mod 17 = 1
x mod 7 = 2
x mod 31 = 3
x mod 23 = 4
We can use the Chinese Remainder Theorem + Modular Multiplicative Inverse to solve the congruences:
1 - The LCM [ 17, 7, 31, 23] = 84,847
2 - 84,847/17 =4,991, 84,847/7 =12,121, 84,847/31 =2,737, 84,847/23 =3,689 [The quotients]
3 - We have to find the Modular Multiplicative Inverses(MMIs) of the quotients in 2 above:
4 - MMI of 4,991 mod 17 =12, MMI of 12,121 mod 7 = 2, MMI of 2,737 mod 31 = 7 and MMI of 3,689 mod 23 = 18
5 - We multiply the remainders x The quotients in 2 above x MMIs in 4 above and sum them all up.
6 - x =[1.4991.12] + [2.12121.2] + [3.2737.7] + [4.3689.18] = 431,461
7 - We take 431,461 mod(LCM) 84,847 =7,226 - which is the smallest positive integer that satifies the 4 congruences.
8 - The full answer is: LCM [84,847n + 7,226], where n =0, 1, 2, 3.......etc.
