+0  
 
0
43
1
avatar

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.

 Feb 11, 2020
 #1
avatar
0

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.

 Feb 11, 2020

31 Online Users