Maths Olympiad Prep

Library / /393 of 520

Number theory Difficulty 6.5 National olympiad Find the answer

4. Solve the following congruences:
(i) 258x131(mod348)258 x \equiv 131 \pmod{348}.
(ii) 3x10(mod29)3 x \equiv 10 \pmod{29}.
(iii) 47x89(mod111)47 x \equiv 89 \pmod{111}.
(iv) 660x595(mod1385)660 x \equiv 595 \pmod{1385}.

Solution

4.
(i) Solution: Since
(258,348)=6,(258,348)=6,

and 61316 \nmid 131, so by Lemma 11, the congruence has no solution.
(ii) Solution: Since
29=9×3+2,3=2+129=9 \times 3+2, \quad 3=2+1

Therefore,
1=32=3(299×3)=10×3291=3-2=3-(29-9 \times 3)=10 \times 3-29

That is,
3×101(mod29)3 \times 10 \equiv 1(\bmod 29)

From the original equation,
3×10x10×10(mod29)3 \times 10 x \equiv 10 \times 10 \quad(\bmod 29)

Thus,
x10013(mod29)x \equiv 100 \equiv 13 \quad(\bmod 29)
(iii) Solution: Since
111=2×47+17,47=2×17+1317=13+4,13=3×4+1\begin{array}{l} 111=2 \times 47+17, \quad 47=2 \times 17+13 \\ 17=13+4, \quad 13=3 \times 4+1 \end{array}

Therefore,
1=133×4=133×(1713)=4×133×17=4×(472×17)3×17=4×4711×17=4×4711×(1112×47)=26×4711×111\begin{aligned} 1= & 13-3 \times 4=13-3 \times(17-13) \\ = & 4 \times 13-3 \times 17=4 \times(47-2 \times 17)-3 \times 17 \\ = & 4 \times 47-11 \times 17=4 \times 47-11 \times(111 \\ & -2 \times 47)=26 \times 47-11 \times 111 \end{aligned}

That is,
26×471(mod111)26 \times 47 \equiv 1 \quad(\bmod 111)

From the original equation,
26×47x26×89(mod111)26 \times 47 x \equiv 26 \times 89(\bmod 111)

Thus,
x26×8994(mod111)x \equiv 26 \times 89 \equiv 94(\bmod 111)
(iv) Solution: Since
(660,1385)=5(660,1385)=5, and 55955 \mid 595, so by Exercise 3, the equation has five solutions. Now, we first solve
132x119(mod277)132 x \equiv 119(\bmod 277)

Since
277=2×132+13,132=10×13+213=6×2+1\begin{array}{l} 277=2 \times 132+13, \quad 132=10 \times 13+2 \\ 13=6 \times 2+1 \end{array}

Therefore,
1=136×2=136×(13210×13)=61×136×132=61×(2772×132)6×132=61×277128×132\begin{aligned} 1 & =13-6 \times 2=13-6 \times(132-10 \times 13) \\ & =61 \times 13-6 \times 132=61 \times(277-2 \\ & \times 132)-6 \times 132=61 \times 277-128 \times 132 \end{aligned}

That is,
128×1321(mod277)-128 \times 132 \equiv 1(\bmod 277)

From the original equation,
128×132x128×119(mod277)2-128 \times 132 x \equiv-128 \times 119(\bmod 277)_{2}

Thus,
x128×1193(mod277)x \equiv-128 \times 119 \equiv 3 \quad(\bmod 277)

The five solutions to the original congruence are
x3(mod1385)x280(mod1385)x557(mod1385)x834(mod1385)x1111(mod1385)\begin{aligned} x & \equiv 3(\bmod 1385) \\ x & \equiv 280(\bmod 1385) \\ x & \equiv 557(\bmod 1385) \\ x & \equiv 834 \quad(\bmod 1385) \\ x & \equiv 1111 \quad(\bmod 1385) \end{aligned}

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.