Туймаада-2015-А.Голованов

[Navid]

К натуральному числу прибавляют его наибольший собственный делитель, к получившемуся прибавляют его наибольший собственный делитель и т. д. Докажите, что после выполнения нескольких операций получится число, кратное $ 3^ {2000}$

[NSKuber]

Если число $n$ делится на $3$, то:
1) Если оно чётно ($n=2k$, $k$ - наибольший собственный делитель), то $2k\to 3k$, количество троек в разложении на простые увеличилось.
2) Если оно нечётно ($n=3k$, $k$ - наибольший собственный делитель), то $3k\to 4k\to 6k$, число стало чётно и количество троек не изменилось, goto 1.
Таким образом, кратное трём может приобрести сколь угодно множителей-троек.
Если исходное число не кратно трём, но чётно, то см. п.1.
Если исходное число не кратно трём и нечётно, то $n=sk$, где $k$ - наибольший собственный делитель, a $s$ - либо нечётное простое, либо совпадает с $n$ (если $n$ - простое). Тогда за один шаг получаем чётное число $(s+1)k$ или $2n$, с которым уже разобрались.