Question

7) Determine if the following congruences have solution(s) and find the solutions if they exist: a. 22x = 4 mob 29 b. 51x = 21 mob 36 C. 35x = 15 mod 182 d. 131x = 21 mob 77 e. 20x = 16 mob 64

Answer 1

# @ de are to solve the linear congruences .: 221 5 4 mod 29 Since ged (22, 21) =1, the congruence has a unique solution since ged (22, 29) = 1, F integers u, u such that 22u + 2qu=1 Here u=4, 1=-3. Therefore 22(4) +29 (-3) = 1 > 22 (4) = 1 mod 29 and thus ) 22 (16) = 4 mod 29. All solutions are a = 16 mod 29 .. Given problem is 512= 21 mod 36. Since ged (51,36) = 3 and 3/21 Therefore the given engreuence has a solution. . The giren congruence is equivalent to 170 = 7 mod 12 noa, ged (17, 12) = I., Hence the congruence 1923 7 mart 12 has a unique solution. Since ged (17, 12) = 1, 7 integers u, o such that 17 u + 120=1 . Here u= 5, v=-7. Therefore 17 (5) +12(-7) = 1 = 17 (5) = 1 (mod 12) and then 17. (35) = 7 mod 12 = x= 35 is a solution of the engruence 170= 7 mod 12. There are three in congruent solutions of the given congruence. They are x= 35, 35+12, 35+24 ie 35, 47, 59

MARA AWW Given problem isr 35m= 15 mod 182. Here the problem has no solution to the theorem of aed. (a,m) = d, then the linear congruence an= b mod n has no solution if d is not a divisor of b. In the above problem , geol (35, 182) = 7, but 7 doen't divide 15. Hence the problem her no sol? * The given foroblem ir 1310 = 21 mod 77. since ged (131,77) = 1, the congruence hap a unique solution, since ged (131,77)= 1,. F integers uile such that 1310t 770=1, Here u= 10, v=-17 Therefore 131.(10) + 77.6-17) = 1 This implies 131./10) 1 mod 77. , - end thus 131(210) = 21 mod 77. Hence n=210 is a solution. All solutions are = 210 mod 77 de x= FG