Maths Olympiad Prep

Library / /145 of 520

Number theory Difficulty 5.8 AIME, harder Find the answer

2. Specifically explain that the method given in question 1 provides a new way to find the greatest common divisor (a,b)(a, b) and solve the linear Diophantine equation ax+by=ca x+b y=c. Use this method to solve the following greatest common divisors and linear Diophantine equations: □\square
(i) 205x+93y=1205 x+93 y=1;
(ii) 65x−56y=−165 x-56 y=-1;
(iii) 13x+17y=513 x+17 y=5;
(iv) 77x+63y=4077 x+63 y=40;
(v) (314,159)(314,159);
(vi) (4144,7696)(4144,7696).

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

Solution

2. (i) 205/93=⟨2,93/19⟩=⟨2,4,19/17⟩=⟨2,4,1,17/2⟩=⟨2,4,1,8,2⟩205 / 93=\langle 2,93 / 19\rangle=\langle 2,4,19 / 17\rangle=\langle 2,4,1,17 / 2\rangle=\langle 2,4,1,8,2\rangle. ⟨2,4,1,8⟩=⟨2,4,9/8⟩=⟨2,44/9⟩=97/44\langle 2,4,1,8\rangle=\langle 2,4,9 / 8\rangle=\langle 2,44 / 9\rangle=97 / 44. From the first question, we know that 205⋅44−93⋅97=−1=−(205,93)205 \cdot 44 - 93 \cdot 97 = -1 = -(205,93), so the solution is x=−44+93t,y=97−205t,t=0,±1,±2,⋯x = -44 + 93t, y = 97 - 205t, t = 0, \pm 1, \pm 2, \cdots. The other questions can be solved using the same method. (iv) No solution.

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.