Given a natural number n, find a formula for the number of k less than n such that k is coprime to n. Prove that the formula works.