Maths Olympiad Prep

Library / /209 of 520

Number theory Difficulty 6.0 AIME, harder Find the answer

Example 9 Find the integer solution of 256x179(mod337)256 x \equiv 179(\bmod 337).

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Since (256,337)=1(256,337)=1, by Lemma 12 we know that 256x256 x \equiv 179(mod337)179(\bmod 337) has integer solutions. Since 337=256+81,256=81×337=256+81,256=81 \times 3+13,81=13×6+3,13=4×3+13+13,81=13 \times 6+3,13=4 \times 3+1, we get 1=131=13 4×3=134×(8113×6)=25×134×81=4 \times 3=13-4 \times(81-13 \times 6)=25 \times 13-4 \times 81= 25×(25681×3)4×81=25×25679×8125 \times(256-81 \times 3)-4 \times 81=25 \times 256-79 \times 81 \Rightarrow 25×25679×(337256)=104×25679×33725 \times 256-79 \times(337-256)=104 \times 256-79 \times 337. Therefore, we have
104×2561(mod337)104 \times 256 \equiv 1(\bmod 337)

By 256x179(mod337)256 x \equiv 179(\bmod 337) and Lemma 5, we have
104×256x104×179(mod337)104 \times 256 x \equiv 104 \times 179 \quad(\bmod 337)

Since 104×179=55×337+81104 \times 179=55 \times 337+81, we get
104×17981(mod337)104 \times 179 \equiv 81(\bmod 337)

From (32) to (34), we get x81(mod337)x \equiv 81(\bmod 337).

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.