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

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