STEP II/2005/2

For any positive integer N, the function f(N) is defined by

f(N) = N\Big(1-\frac1{p_1}\Big)\Big(1-\frac1{p_2}\Big) \cdots\Big(1-\frac1{p_k}\Big)

where p_1, p_2, \dots , p_k are the only prime numbers that are factors of N.

Thus f(80)=80(1-\frac{1}{2})(1-\frac{1}{5})\,

(1) Evaluate f(12) and f(180)

(2) Show that f(N) is an integer for all N

(3) Prove, or disprove by means of a counterexample, each of the following:

(a) f(m) f(n) = f(mn)

(b) f(p) f(q) = f(pq) if p and q are distinct prime numbers;

(c) f(p) f(q) = f(pq)  only if p and q are distinct prime numbers.

(4) Find a positive integer m and a prime number p such that

f(p^m) = 146410

Click here for a solution

f(n) is the Euler totient function: more here.

In fact f(m).f(n) = f(mn) iff m and n are coprime (share no prime factor).