Skip to main content.

Second hint to puzzle 152: Totient valence

A number of steps are needed to evaluate v(21000)...

Note that, if k = p1a1 · p2a2 ·...· prar, then phi(k) = (p1a1 − p1a1−1)·(p2a2 − p2a2−1)·...·(prar − prar−1).  (1)

Show that:

Let k be such that phi(k) = 2m, for some m.  Show that, if p is a prime that divides k, then p − 1 = phi(p) divides phi(k) = 2m.  Hence the primes that make up k are of the form 2t + 1.  (Note that if 2t + 1 is prime then t is a power of 2.)  Then use (1) to find all odd k such that phi(k) = 2m, for m < 32.