Функции в натуральных/целых/рациональных числах

Подсказка 1

Сначала попробуем понять, чему равно g(1). Какие n и k надо для этого взять?

Подсказка 2

Возьмём n = k = 1, получим g(1) = 1. Может ли функция g принимать значение 1 в каких-то других точках?

Подсказка 3

На самом деле не может, иначе получаем противоречие из формулы gₙ(n) = n (gₙ(n) — n-ая итерация функции g). Тогда для каждого составного n g(n) является тоже составным числом. А что если n — простое число?

Подсказка 4

В простых точках функция возвращает простые числа, ведь если это не так, то для простого p опять получаем противоречие из gₚ(p) = p. Пусть k — минимальное число, такое что gₖ(p) = p. Как можно связать k и p?

Подсказка 5

Попробуйте поиграться с вложением функций в равенстве gₚ(p) = p, используя идею деления p на k с остатком, чтобы получить противоречие с минимальностью k. Отсюда выведите, что либо k = 1, либо k = p (т.е. k - делитель p). Рассмотрите случай k = p.

Подсказка 6

Используйте идею из предыдущей подсказки, чтобы доказать, что k делит ещё одно простое число, а именно g(p). Тогда k = 1 и для любого простого p g(p) = p. Какой вывод тогда можно сделать для любого натурального n?

Подсказка 7

Воспользуемся условием g(nk) = g(n)g(k) и основной теоремой арифметики, получим, что g(n) = n для любого n ∈ ℕ. Задача решена!