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

При имеем откуда Из условия следует, что больше ни при каких других функция не принимает значение ( — -я итерация функции ).

Тогда понятно, что из каждого составного числа функция возвращает составное число: Предположим, что в простых точках функция также возвращает составные числа, но тогда при простом число должно быть составным, противоречие. Значит в простых точках функция является простым числом.

Пусть — такое минимальное число, что В таком случае, должно быть делителем иначе — остаток от деления на Заметим, что а мы выбрали наименьшим таким, что Это означает, что либо либо Предположим, что тогда пусть — простое, отличное от Заметим, что справедливо равенство Если вместо подставить то получим значит делит То есть — общий делитель двух простых чисел, откуда Но тогда при любом простом имеем

Осталось лишь воспользоваться условием и ОТА для того, чтобы убедиться в том, что при любом натуральном