Answer:
a) 23 x 36 (mod 55) = 3 (mod 55)
b) 23 x 36 (mod 55) = 23 (mod 91)
Step-by-step explanation:
The Chinese Remainder Theorem lets us split a composite modulo into its prime components and solve for smaller numbers.
a) Using the Chinese Remainder Theorem, we have that 55 = 11 x 5
Since 11 and 5 are relatively prime numbers, we can use the Theorem and rewrite 23 x 36 mod 55 as: 23 x 36 (mod 11) and 23 x 36 (mod 5).
First we will work with 23 x 36 (mod 11)
[tex](23)(36)(mod 11) = (1)(3) (mod 11)[/tex] (Since 23 is congruent to 1 modulo 11 and 36 is congruent to 3 modulo 11)
Now we do the same with 23 x 36 (mod 5)
[tex](23)(36) (mod 5) = (3)(1) (mod5) = 3 (mod 5)[/tex]
Now we will use the Chinese Remainder Theorem to solve this pair of equations:
x = 3 (mod 11) and x = 3(mod 5)
[tex]x=5y+3\\5y+3=3(mod 11)\\5y=0(mod 11)\\y=0 (mod 11)\\y=11z\\x=5(11z)+3\\x=55z + 3\\x=3(mod 55)\\[/tex]
b) We are going to use the same procedure from a)
91 = 13 x 7
29 x 51 (mod 91) = 29 x 51 (mod 13) and 29 x 51 (mod 7)
29 x 51 (mod 13) = 3 x 12 (mod 13) = 36 (mod 13) = 10 (mod 13)
29 x 51 (mod 7) = 1 x 2 (mod 7) = 2 (mod 7)
Our pair of equations is x = 10 (mod 13) and x = 2 (mod 7)
[tex]x= 7y + 2\\7y + 2 = 10(mod13)\\7y= 8(mod13)\\y= 3 (mod 13)\\y=13y+3\\x=7(13y+3) + 2\\x=91y +21+2\\x=91y+23\\x= 23 (mod 91)[/tex]
