|
|
 |
Условие
В ячейку памяти компьютера записали число 6. Далее компьютер делает миллион шагов. На шаге номер n он увеличивает число в ячейке на наибольший общий делитель этого числа и n. Докажите, что на каждом шаге компьютер увеличивает число в ячейке либо на 1, либо на простое число.
Решение
Обозначим через an число после n-го шага. Пусть на каком-то шаге an = 3n (например, a3 = 9). Пусть после этого число p, большее 1, впервые прибавилось на m-м шаге.
Тогда до этого прибавлялись единицы, то есть am–1 = m + 2n – 1.
Поэтому p = НОД(m, m + 2n – 1) = НОД(m, 2n – 1). Ясно, что p нечётно: p = 2l – 1.
Так как 2n – 1 ≡ 0 (mod p), то 2n ≡ 1 ≡ 2l (mod p), то есть n ≡ l (mod 2l – 1). Следовательно,
m = n + l – 1 = n + ½ (p – 1) (это наименьшее число, большее n и кратное p).
Пусть q – наименьший простой множитель числа 2n – 1, k = n + ½ (q – 1) = ½ (2n – 1 + q) ≤ m. Это число кратно q. Тогда ak–1 = k + 2n – 1, а
НОД(k, k + 2n – 1) = НОД(k, 2n – 1) делится на q. Таким образом, прибавление "не единицы" происходит на k-м шаге. Это значит, что k = m, а q = p.
Замечания
9 баллов
