Given a prime we'll define to be the maximum integer such that (it's 0 if p doesn't divide n)

First note that if and only if for all primes (use the prime descomposition)

But we also have for all . Using these 2 results you should not have problems in finding a proof.