Final answer:
To solve the congruences, we need to find the multiplicative inverses modulo the given numbers. For each congruence, we can use the Extended Euclidean Algorithm to find the inverses. Then, we substitute the inverses into the congruences to find the solutions.
Step-by-step explanation:
a) 34x = 77 mod 89:
To solve this congruence, we need to find the multiplicative inverse of 34 modulo 89. Let's call this inverse 'a'. We can find 'a' by using the Extended Euclidean Algorithm:
89 = 2 * 34 + 21
34 = 1 * 21 + 13
21 = 1 * 13 + 8
13 = 1 * 8 + 5
8 = 1 * 5 + 3
5 = 1 * 3 + 2
3 = 1 * 2 + 1
2 = 2 * 1 + 0
From the algorithm, we can see that the gcd(34, 89) is 1, which means that 34 has an inverse modulo 89.
Solving backwards, substituting 'a' into the congruence, we get:
x = 77 * a mod 89
x = 77 * 64 mod 89
x = 4928 mod 89
x = 55 mod 89
So, the solution to the congruence is x = 55.
b) 144r ≡ 4 mod 233:
To solve this congruence, we can multiply both sides of the congruence by the multiplicative inverse of 144 modulo 233. Let's call this inverse 'b'. We can find 'b' using the same method as in the previous congruence:
233 = 1 * 144 + 89
144 = 1 * 89 + 55
89 = 1 * 55 + 34
55 = 1 * 34 + 21
34 = 1 * 21 + 13
21 = 1 * 13 + 8
13 = 1 * 8 + 5
8 = 1 * 5 + 3
5 = 1 * 3 + 2
3 = 1 * 2 + 1
2 = 2 * 1 + 0
From the algorithm, we can see that the gcd(144, 233) is 1, which means that 144 has an inverse modulo 233.
Solving backwards, substituting 'b' into the congruence, we get:
r ≡ 4 * b mod 233
r ≡ 4 * 169 mod 233
r ≡ 676 mod 233
r ≡ 210 mod 233
So, the solution to the congruence is r ≡ 210.
c) 200r ≡ 13 mod 1001:
To solve this congruence, we can multiply both sides of the congruence by the multiplicative inverse of 200 modulo 1001. Let's call this inverse 'c'. We can find 'c' using the same method as in the previous congruences:
1001 = 5 * 200 + 1
200 = 200 * 1 + 0
From the algorithm, we can see that the gcd(200, 1001) is 1, which means that 200 has an inverse modulo 1001.
Solving backwards, substituting 'c' into the congruence, we get:
r ≡ 13 * c mod 1001
r ≡ 13 * 801 mod 1001
r ≡ 10413 mod 1001
r ≡ 84 mod 1001
So, the solution to the congruence is r ≡ 84.