84.8k views
0 votes
Solve the following congruences. show your work to receive proper credit!

a) 34x = 77 mod 89 b) 144r 4 mod 233 c) 200r = 13 mod 1001

User Etudor
by
8.3k points

1 Answer

6 votes

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.

User SanthoshPrasad
by
7.6k points

Related questions

asked Dec 13, 2024 226k views
Omarjmh asked Dec 13, 2024
by Omarjmh
8.6k points
2 answers
3 votes
226k views
1 answer
2 votes
157k views