Математикадан «Туймаада» олимпиадасы. Жоғары лига. 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$ ЧТД