Maths Olympiad Prep

Library / /221 of 520

Number theory Difficulty 6.0 National olympiad Find the answer

Example 5 Solve the congruence equation 19x556(mod1155)19 x \equiv 556(\bmod 1155).

A number or a short expression. Spacing and $ signs are ignored.

Solution

This is a linear congruence equation, which can of course be solved using the method in §2. Here, we transform it into a system of linear congruence equations with smaller moduli, which is sometimes more convenient. Since 1155=357111155 = 3 \cdot 5 \cdot 7 \cdot 11, by the property [X] in Chapter 3 §1, this congruence equation has the same solution as the system of congruence equations

Using the equivalent transformation I in §1, this system of congruence equations becomes
x1(mod3),x1(mod5)2x3(mod7),3x6(mod11)\begin{aligned} x \equiv 1(\bmod 3), & & -x \equiv 1(\bmod 5) \\ -2 x \equiv 3(\bmod 7), & & -3 x \equiv 6(\bmod 11) \end{aligned}

Furthermore, using the equivalent transformations III and I of 11 (i.e., solving the second, third, and fourth equations in the above system of congruence equations), the system of congruence equations becomes
x1(mod3),x1(mod5)x2(mod7),x2(mod11)\begin{array}{ll} x \equiv 1(\bmod 3), & x \equiv -1(\bmod 5) \\ x \equiv 2(\bmod 7), & x \equiv -2(\bmod 11) \end{array}

This system of congruence equations can be solved using the method in Theorem 1. In fact, this is the system of congruence equations in our Example 1, and its solution is
x394(mod1155)x \equiv 394(\bmod 1155)

This is the solution to the original congruence equation.
19x556(mod3),19x556(mod5),19x556(mod7),19x556(mod11)\begin{array}{l} 19 x \equiv 556(\bmod 3), \quad 19 x \equiv 556(\bmod 5), \\ 19 x \equiv 556(\bmod 7), \quad 19 x \equiv 556(\bmod 11) \end{array}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.