Математикадан «Туймаада» олимпиадасы. Кіші лига. 2015 жыл

Натурал санға, оның ең үлкен бөлгішін қосады, пайда болған санға осы санның ең ұлкен бөлгішін қосады, және т.т. Осындай бірнеше амал орындағаннан кейін, пайда болған сан ${{3}^{2000}}$-не бөлінетінін дәлелдеңіз. ( А. Голованов )

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

Рассмотрим число $2^a3^b$ $(a>0,b\geq 0)$:

$$2^a3^b\to 2^a3^b+2^{a-1}3^b=2^{a-1}3^{b+1}\to ...\to 3^{a+b}\to 4\cdot 3^{a+b-1}\to 2\cdot 3^{a+b}\to 3^{a+b+1}\to ...\to 3^{a+b+c},$$

откуда получается, что в какой-то момент $a+b+c$ будет больше $2000$. $(A)$

Если изначальное число $2^a3^bk$ $(2,3\nmid k, a>0, b\geq 0)$, то раз $k>3$, получается, что все сводиться $(!)$ к $(A)$, так как $2^a3^bk\to 2^{a-1}3^{b+1}k$. $(B)$

Если $2,3\nmid \alpha$, то $\alpha\to \alpha+\beta$, где $2\nmid \alpha, \beta\Leftrightarrow \alpha+\beta=2k$, что приводит к $(B)$.

Отсюда следует требуемое.

Пусть $\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$ ЧТД