Олимпиада Туймаада по математике. Младшая лига. 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$ ЧТД