Математикадан республикалық олимпиада, 2008-2009 оқу жылы, 11 сынып
Комментарий/решение:
222...2=((((2)2)2)...)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, а умножение на явно большую степень двойки даёт требуемое. В частности из этого следует утверждение задачи
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.