5

Part of 2015 Tuymaada Olympiad

Problems(1)

Number and divisor

Source: Tuymaada 2015, Day 2, Problem 5, Senior League

There is some natural number

n>1

on the board. Operation is adding to number on the board it maximal non-trivial divisor. Prove, that after some some operations we get number, that is divisible by

3^{2000}