Use the CRT to solve the linear congruence 17x = 9 (mod 276).
Using the Chinese Remainder Theorem Solve the following:
Here is the theorem first:
Chinese Remainder Theorem (CRT): Let r, m1, . . . , mr ∈ Z and for all 1 ≤ i ̸= j ≤ r
suppose gcd(mi, mj ) = 1. Then for any r integers a1, . . . , ar, the system of linear
congruences
x = a1 (mod m1)
x = a2 (mod m2)
.
.
.
x = ar (mod mr)
has a solution x ∈ Z and it is unique modulo m1m2 · · · mr, i.e. if y ∈ Z is any other
solution, then y = x (mod m1m2 · · · mr).
Problems:
1. Use the CRT to solve the linear congruence 17x = 9 (mod 276).
2. Find three consecutive integers, each of which contains at least one perfect square factor.
3. Find the smallest integer a > 2 such that 2 | a, 3 | a + 1, 4 | a + 2,5 | a + 3, and 6 | a + 4,
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 2 images
