Олимпиада Туймаада по математике. Старшая лига. 2015 год

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

Комментарий/решение

Пусть $\nu_p(x)$ это степень вхождения $p$ на $x$

Введем функцию

$f(n)=n+d$ там где $d$ наибольший делитель $n$

(ну это шаг который нам дали в условии) Заметим, что если $d$ наибольший делитель $n$, то $\dfrac{n}{d}=p$ тоже делитель $n$, причем наименьший. Если вдруг $p \notin \mathbb{P}$ то пусть $a \mid p \ (1<a<p)$ то $a \mid p \mid n \Rightarrow a \mid n$ но мы сказали, что $p$ наименьший делитель. Противоречие. Значит $p$ простой

Теперь поймем, что $f(n)=n+d=n+\dfrac{n}{p}=\dfrac{n(p+1)}{p} \Rightarrow \\ f(n)=\dfrac{n(p+1)}{p}$ запомните этот факт, дальше оно будет использоваться без упоминания во всех 3 случаях

Теперь случай

$1)p=2 \Rightarrow \nu _3(n)+1=\nu_3(f(n))$

$2)p=3 \Rightarrow p+1=4$ значит $\nu_3(n)-1=\nu_3(f(n))$ но $f(n)=\dfrac{4n}{3}$ получается наименьший делитель $f(n)$ будет $2$ а как мы помним с 1 случай, $\nu_3(f(n))+1=\nu_3(f(f(n)))$ (там просто 2 была наименьшим для $n$, а тут для $f(n)$)

$f(f(n))=f(n)+ \dfrac{f(n)}{2}$ мы помним, что $f(n)$ делится на 4 значит четный+четный=четный, значит $f(f(n))$ тоже четный т.е. наименьший делитель $2$ тогда $\nu_3(f(f(n)))+1=\nu_3(f(f(f(n))))$

Тогда $\nu_3(n)-1=\nu_3(f(n))=\nu_3(f(f(n)))-1=\nu_3(f(f(f(n))))-2 \Rightarrow \nu_3(n)+1=\nu_3(f(f(f(n))))$

$3)p>3 \Rightarrow p+1$ четный, значит $f(n)$ тоже четный, значит наименьший делитель $2$, причем значит $\nu_3(n)+1=\nu_3(f(n))$ тогда мы поняли, что степень вхождения $3$ растет в любом случае, значит когда нибудь достигнет $2000$ ЧТД