Competition problem — Number theory

Library / /59 of 520

Number theory Difficulty 5.5 AIME, harder Find the answer

Example 2 Since $(72,157)=1$ , by Lemma 1 there must be two integers $x$ , $y$ that satisfy
$72 x+157 y=1$

established, find $x, y$ .

Your answer

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

Solution

Since
$\begin{array}{l} 157=2 \times 72+13, \quad 72=5 \times 13+7 \\ 13=7+6, \quad 7=6+1 \end{array}$

we get
$\begin{aligned} 1 & =7-6=7-(13-7)-2 \times 7-13 \\ & =2 \times(72-5 \times 13)-13=2 \times 72-11 \times 13 \\ & =2 \times 72-11 \times(157-2 \times 72) \\ & =24 \times 72-11 \times 157=72 \times 24-157 \times 11 \end{aligned}$

Therefore,
$x=24, \quad y=-11$

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.