Is it true that k=f(n), where f(n) is Euler function?

Edited by author 13.02.2009 22:03

Yes =)
2 ADMINS: don't delete this hint. Really, it's easy to think it out - harder is to write

If anyone got stuck with this.

here is the well-known formula for computing phi function:

phi(n) = product of [ p^{a - 1} * (p - 1) ], where factorized n = product [ p^a ].

The problem has a pretty fast brute force solution. Once you find a number K such that (K + 1) is prime and K divides phi(n) try to construct n with this prime (multiply by (K + 1) once and continue while phi(n) / (K + 1)^b is a multiple of (K + 1)).