Maths Olympiad Prep

Library / /251 of 520

Number theory Difficulty 5.5 AIME, harder Find the answer

Example 1 Solve the system of congruences
{x1(mod3)x1(mod5)x2(mod7)x2(mod11) \left\{\begin{array}{l} x \equiv 1(\bmod 3) \\ x \equiv -1(\bmod 5) \\ x \equiv 2(\bmod 7) \\ x \equiv -2(\bmod 11) \end{array}\right.

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

Solutions — 3

Solution 1

Let m1=3,m2=5,m3=7,m4=11m_{1}=3, m_{2}=5, m_{3}=7, m_{4}=11, then M1=5711,M2=3711,M3=M_{1}=5 \cdot 7 \cdot 11, M_{2}=3 \cdot 7 \cdot 11, M_{3}= 3511,M4=3573 \cdot 5 \cdot 11, M_{4}=3 \cdot 5 \cdot 7.
Also, M1(1)(1)(1)1(mod3)M_{1} \equiv(-1) \cdot(1) \cdot(-1) \equiv 1(\bmod 3),
so 1M1M11M11(mod3)1 \equiv M_{1} M_{1}^{-1} \equiv M_{1}^{-1}(\bmod 3), we can take M11=1M_{1}^{-1}=1.
By M2(2)(2)(1)1(mod5)M_{2} \equiv(-2) \cdot(2) \cdot(1) \equiv 1(\bmod 5),
so 1M2M21M21(mod5)1 \equiv M_{2} M_{2}^{-1} \equiv M_{2}^{-1}(\bmod 5), we can take M21=1M_{2}^{-1}=1.
By M33×5×44(mod7)M_{3} \equiv 3 \times 5 \times 4 \equiv 4(\bmod 7),
so 1M3M314M31(mod7)1 \equiv M_{3} M_{3}^{-1} \equiv 4 M_{3}^{-1}(\bmod 7), we can take M31=2M_{3}^{-1}=2.
By M43×5×74×76(mod11)M_{4} \equiv 3 \times 5 \times 7 \equiv 4 \times 7 \equiv 6(\bmod 11),
so 1M4M416M41(mod11)1 \equiv M_{4} M_{4}^{-1} \equiv 6 M_{4}^{-1}(\bmod 11), we can take M41=2M_{4}^{-1}=2.
By the Chinese Remainder Theorem, the solution to the system of congruences is
x=(5711)11+(3711)1(1)+(3511)22+(357) x=(5 \cdot 7 \cdot 11) \cdot 1 \cdot 1+(3 \cdot 7 \cdot 11) \cdot 1 \cdot(-1)+(3 \cdot 5 \cdot 11) \cdot 2 \cdot 2+(3 \cdot 5 \cdot 7)
- 2(2)(mod35711)2 \cdot(-2)(\bmod 3 \cdot 5 \cdot 7 \cdot 11),
which is x394(mod1155)x \equiv 394(\bmod 1155).

Solution 2

Let m1=3,m2=5,m3=7,m4=11m_{1}=3, m_{2}=5, m_{3}=7, m_{4}=11, satisfying the conditions of Theorem 1. In this case, M1=5711,M2=3711,M3=3511,M4=357M_{1}=5 \cdot 7 \cdot 11, M_{2}=3 \cdot 7 \cdot 11, M_{3}=3 \cdot 5 \cdot 11, M_{4}=3 \cdot 5 \cdot 7. We will find Mj1M_{j}^{-1}. Since M1(1)(1)(1)1(mod3)M_{1} \equiv(-1) \cdot(1) \cdot(-1) \equiv 1(\bmod 3), we have
1M1M11M11(mod3)1 \equiv M_{1} M_{1}^{-1} \equiv M_{1}^{-1}(\bmod 3)

Therefore, we can take M11=1M_{1}^{-1}=1. From M2(2)(2)11(mod5)M_{2} \equiv(-2) \cdot(2) \cdot 1 \equiv 1(\bmod 5), we have
1M2M21M21(mod5)1 \equiv M_{2} M_{2}^{-1} \equiv M_{2}^{-1}(\bmod 5)

Therefore, we can take M21=1M_{2}^{-1}=1. From M33544(mod7)M_{3} \equiv 3 \cdot 5 \cdot 4 \equiv 4(\bmod 7), we have
1M3M314M31(mod7)1 \equiv M_{3} M_{3}^{-1} \equiv 4 M_{3}^{-1}(\bmod 7)

Therefore, we can take M31=2M_{3}^{-1}=2. From M4357476(mod11)M_{4} \equiv 3 \cdot 5 \cdot 7 \equiv 4 \cdot 7 \equiv 6(\bmod 11), we have
1M4M416M41(mod11)1 \equiv M_{4} M_{4}^{-1} \equiv 6 M_{4}^{-1}(\bmod 11)

Therefore, we can take M41=2M_{4}^{-1}=2. Thus, by Theorem 1, the solution to the system of congruences is
x(5711)11+(3711)1(1)+(3511)22+(357)2(2)(mod35711),\begin{aligned} x \equiv & (5 \cdot 7 \cdot 11) \cdot 1 \cdot 1+(3 \cdot 7 \cdot 11) \cdot 1 \cdot(-1)+(3 \cdot 5 \cdot 11) \cdot 2 \cdot 2 \\ & +(3 \cdot 5 \cdot 7) \cdot 2 \cdot(-2)(\bmod 3 \cdot 5 \cdot 7 \cdot 11), \end{aligned}

i.e., \square
x385231+660420394(mod1155)x \equiv 385-231+660-420 \equiv 394(\bmod 1155)

Solution 3

Let m1=3,m2=5,m3=7,m4=11m_{1}=3, m_{2}=5, m_{3}=7, m_{4}=11, then M1=5711,M2=3711,M3=M_{1}=5 \cdot 7 \cdot 11, M_{2}=3 \cdot 7 \cdot 11, M_{3}= 3511,M4=3573 \cdot 5 \cdot 11, M_{4}=3 \cdot 5 \cdot 7

From M1(1)(1)(1)1(mod3)M_{1} \equiv(-1) \cdot(1) \cdot(-1) \equiv 1(\bmod 3),
so 1M1M11M11(mod3)1 \equiv M_{1} M_{1}^{-1} \equiv M_{1}^{-1}(\bmod 3), we can take M11=1M_{1}^{-1}=1.
From M2(2)(2)(1)1(mod5)M_{2} \equiv(-2) \cdot(2) \cdot(1) \equiv 1(\bmod 5),
so 1M2M21M21(mod5)1 \equiv M_{2} M_{2}^{-1} \equiv M_{2}^{-1}(\bmod 5), we can take M21=1M_{2}^{-1}=1.
From M33×5×44(mod7)M_{3} \equiv 3 \times 5 \times 4 \equiv 4(\bmod 7),
so 1M3M314M31(mod7)1 \equiv M_{3} M_{3}^{-1} \equiv 4 M_{3}^{-1}(\bmod 7), we can take M31=2M_{3}^{-1}=2.
From M43×5×74×76(mod11)M_{4} \equiv 3 \times 5 \times 7 \equiv 4 \times 7 \equiv 6(\bmod 11),
so 1M4M416M41(mod11)1 \equiv M_{4} M_{4}^{-1} \equiv 6 M_{4}^{-1}(\bmod 11), we can take M41=2M_{4}^{-1}=2.
By the Chinese Remainder Theorem, the solution to the system of congruences is
x=(5711)11+(3711)1(1)+(3511)22+(357)x=(5 \cdot 7 \cdot 11) \cdot 1 \cdot 1+(3 \cdot 7 \cdot 11) \cdot 1 \cdot(-1)+(3 \cdot 5 \cdot 11) \cdot 2 \cdot 2+(3 \cdot 5 \cdot 7)
- 2(2)(mod35711)2 \cdot(-2)(\bmod 3 \cdot 5 \cdot 7 \cdot 11)

which is x394(mod1155)x \equiv 394(\bmod 1155).

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.