42.2k views
1 vote
5. [Chinese Remainder Theorem, 10pt] Use the method of the Chinese Remainder Theorem to solve the following problems. Show your work.

a) [6pt] Find x (between 0 and 3279*1072)

such that

x ≡ 1072 (3279), and x ≡ 77 (2303).

b) [4pt] Find x (between 0 and 5696 * 4803 * 4531)

such that

x ≡ 1072 (3279), x ≡ 77 (2303). and x ≡ 4545 (6731).

User Mik Jagger
by
8.3k points

1 Answer

6 votes

a) We want to solve the system of congruences:

x ≡ 1072 (3279)

x ≡ 77 (2303)

First, we find the solutions to the two congruences separately. For the first congruence, we have:

3279 = 5 * 2303 + 674

So we can write:

x ≡ 1072 (3279) ≡ 1072 (5 * 2303 + 674) ≡ 1072 (674) (mod 2303)

We can use the Euclidean algorithm to find the inverse of 674 modulo 2303:

2303 = 3 * 674 + 281

674 = 2 * 281 + 112

281 = 2 * 112 + 57

112 = 2 * 57 - 2

Working backwards, we have:

1 = 3 - 2 * (674 - 2 * (281 - 2 * 112 + 2)) = 7 * 674 - 6 * 2303

So we can multiply both sides of the congruence by 674 and simplify:

x ≡ 1072 (674) (mod 2303)

x ≡ 722 (mod 2303)

Now, we can use the same method to solve the second congruence:

2303 = 29 * 77 + 42

77 = 1 * 42 + 35

42 = 1 * 35 + 7

35 = 5 * 7 + 0

Working backwards, we have:

1 = -1 * 29 + 2 * 7

= -1 * 29 + 2 * (42 - 1 * 35)

= 2 * 42 - 3 * 35

= 2 * 42 - 3 * (77 - 42)

= -3 * 77 + 5 * 42

= -3 * 77 + 5 * (2303 - 29 * 77)

= -152 * 77 + 5 * 2303

So we can multiply both sides of the congruence by 152 and simplify:

x ≡ 77 (152) (mod 2303)

x ≡ 497 (mod 2303)

Now we have two congruences that we can solve using the Chinese Remainder Theorem. We need to find integers a and b such that:

x ≡ a (3279 * 2303)

x ≡ b (674 * 152)

To find a, we can use the formula:

a = (77 * 3279 * 152 + 1072 * 674 * 2303) mod (3279 * 2303)

To find b, we can use the formula:

b = (1072 * 674 * 152 + 497 * 3279 * 2303) mod (674 * 152)

Evaluating these formulas, we get:

a = 2258536

b = 602064

So the solution to the system of congruences is:

x ≡ 2258536 (mod 3279 * 2303)

x ≡ 602064 (mod 674 * 152)

To find the unique solution x between 0 and 3279 * 1072, we can use the formula:

x = a + (b - a) * (3279 * 2303) * (674 * 152)^(-1) mod (3279 * 1072)

where (674 * 152)^(-1) is the inverse of 674 * 152 modulo 3279 * 1072. We can find this inverse using the Euclidean algorithm:

3279 * 1072 = 3 * 674 * 152 + 536064

674 * 152 = 1 * 536064 + 36320

536064 = 14 * 36320 + 4944

36320 = 7 * 4944 + 272

4944 = 18 * 272 + 240

272 = 1 * 240 + 32

240 = 7 * 32 + 16

32 = 2 * 16 + 0

Working backwards, we have:

1 = 2 - 1 * 1

= 2 - 1 * (32 - 2 * 16)

= -1 * 32 + 3 * 16

= -1 * 32 + 3 * (240 - 7 * 32)

= 22 * 32 - 3 * 240

= 22 * (272 - 240) - 3 * 240

= -25 * 240 + 22 * 272

= -25 * (4944 - 18 * 272) + 22 * 272

= 472 *

User Navindra
by
8.2k points