Республиканская олимпиада по математике, 2009 год, 11 класс

Докажите, что для любого натурального $n\geq2$ , число $ \underbrace{2^{2^{ \dots ^{2}}}}_{n \text{ раз}}-\underbrace{2^{2^{ \dots .^{2}}}}_{n-1 \text{ раз}} $ делится на $n$.

Комментарий/решение

$2^{2^{2^{...^{2}}}} = \left( \left( \left( \left( 2 \right)^2 \right)^2\right)^{...} \right)^2$

Рассмотрим остатки от деления числа $«n-1»$ раз на $n$, остатки от деления числа

$2^2 \equiv a \ mod \ n, \ \ (2^2)^2 \equiv a^2 \equiv b \ \mod \ n$ и т.д будут образовывать цикл, пусть он равен $T < n$ , положим что $\alpha$ некоторое целое число что $2^{2^{\alpha}} \equiv \ c \ \mod \ n$ и $\beta$ также целое , тогда их связывает соотношение вида $2^{2^{\alpha + T \cdot \beta}} = 2^{2^{...^{2}}}$

Откуда $\beta = \frac{2^{2^{2^{...2}}}-\alpha}{T}$ где число $2^{2^{2^{...2}}}$ повторена $«n-3»$ раза.

Докажем что числа $«n»$ и $«n-1»$ раза будут иметь одинаковые остатки по $mod \ n$, для этого надо доказать что числа уже с $«n-2»$ и $«n-3»$ раза будут иметь одинаковые остатки по $\mod \ T$, тогда проделывая аналогичные итерации, получаем вновь цикл с периодом $T_{1}<T<n$ откуда $\beta_{1}=\frac{2^{2^{...2}}-\alpha_{1}}{T_{1}}$ откуда следует что нужно доказать равноостаточность чисел $«n-4»,«n-5»$ по $\mod \ T_{1}$ и т.д сведя все к случаю $T_{i}=1$ получаем что изначальные числа будут иметь одинаковые остатки, значит и разность будет делится на $n$.

По индукции докажем, что последовательность $a_{n+1}=\underbrace{2^{2^{...^2}}}_{\text{$n$ раз}}(2^{a_n}-1), a_1=1$ делится на все числа от 1 до $n+1$. База ясна. Шаг: Поскольку $a_n$ делится на все числа от 1 до $n$, то оно делится на $\varphi(2), \varphi(3),..., \varphi(n+1)$(Здесь используется то, что $1\le\varphi(n)<n$). Поэтому по теореме Эйлера $2^{a_n}-1$ делится на все нечётные натуральные числа, не большие $n+1$, а умножение на явно большую степень двойки даёт требуемое. В частности из этого следует утверждение задачи