Олимпиадные задачи из источника «весенний тур, сложный вариант, 10-11 класс» для 10 класса - сложность 4 с решениями

Дано целое число  <i>n</i> > 1.  Двое игроков по очереди отмечают точки на окружности: первый – красным цветом, второй – синим (отмечать одну и ту же точку дважды нельзя). Когда отмечено по <i>n</i> точек каждого цвета, игра заканчивается. После этого каждый игрок находит на окружности дугу наибольшей длины с концами своего цвета, на которой больше нет отмеченных точек. Игрок, у которого найденная длина больше, выиграл (в случае равенства длин дуг, а также при отсутствии таких дуг у обоих игроков – ничья). Кто из играющих может всегда выигрывать, как бы ни играл противник?

В ячейку памяти компьютера записали число 6. Далее компьютер делает миллион шагов. На шаге номер <i>n</i> он увеличивает число в ячейке на наибольший общий делитель этого числа и <i>n</i>. Докажите, что на каждом шаге компьютер увеличивает число в ячейке либо на 1, либо на простое число.