Maths Olympiad Prep

Library / /20 of 61

Number theory Difficulty 5.3 AIME, harder Prove it Ukraine

Prove that for any positive integer nn the number 5n(5n+1)6n(3n+2n)5^n (5^n + 1) - 6^n (3^n + 2^n) is divisible by 9191.

Solution

Позначимо значення даного виразу через ana_n. Маємо:
an=25n+5n18n12n=(25n18n)(12n5n)==(2518)(25n1+25n218++2518n2+18n1)(125)(12n1+12n25++125n2+5n1). \begin{aligned} a_n &= 25^n + 5^n - 18^n - 12^n = (25^n - 18^n) - (12^n - 5^n) = \\ &= (25 - 18)(25^{n-1} + 25^{n-2} \cdot 18 + \dots + 25 \cdot 18^{n-2} + 18^{n-1}) - \\ &\quad -(12 - 5)(12^{n-1} + 12^{n-2} \cdot 5 + \dots + 12 \cdot 5^{n-2} + 5^{n-1}). \end{aligned}
Оскільки 2518=125=725 - 18 = 12 - 5 = 7, то ana_n ділиться без остачі на 77. Аналогічно,
an=25n+5n18n12n=(25n12n)(18n5n)==(2512)(25n1+25n212++2512n2+12n1)(185)(18n1+18n25++185n2+5n1), \begin{aligned} a_n &= 25^n + 5^n - 18^n - 12^n = (25^n - 12^n) - (18^n - 5^n) = \\ &= (25 - 12)(25^{n-1} + 25^{n-2} \cdot 12 + \dots + 25 \cdot 12^{n-2} + 12^{n-1}) - \\ &\quad -(18 - 5)(18^{n-1} + 18^{n-2} \cdot 5 + \dots + 18 \cdot 5^{n-2} + 5^{n-1}), \end{aligned}
тому ana_n ділиться без остачі на 1313. Оскільки 77 і 1313 взаємно прості, то ana_n ділиться без остачі на 713=917 \cdot 13 = 91.

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: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.