il Pove that the congnences 11 Prove that the congruences a

/il. Pove that the congnences 11. Prove that the congruences a (mod n) and x b (mod m) r admit a simultaneous solution if and only if ged(n, m) a-b; if a solution exists, confirm that it is unique modulo lcm(n, m). 12. Use Problem 11 to show that the following system does not possess a solution: r 5 (mod 6) and x 7 (mod 15)

Solution

Consider the given system

x 5( mod 6 ) and x 7( mod 15 )

Use (11) ,  

the system of congruences x a ( mod n ) and x b ( mod m ) has a solution if and only if gcd( n ,m )|(a b).

plug in a = 5 , b = 7 , n = 6 and m = 15 then

gcd ( 6 , 15 ) | ( 5 - 7 )

= 3 | ( -2 ) which is not true since 3 does not divide - 2 .

Hence the given system

x 5( mod 6 ) and x 7( mod 15 ) does not possess a solution