Задача
В ячейку памяти компьютера записали число 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. При этом am = am–1+p = m+ 2n– 1 +p = m+ 2m= 3m. Значит, и в следующий раз прибавится простое число. И т.д.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь