Еще раз - если судить по тому, что написано на вики, нужна функция Эйлера в очень частном случае, для придумывания которого знание того, что это такое никак не помогает.

Как связано слово "ф-я Эйлера" с информацией о том, насколько сложно раскладывать число на простые множители? Может я тут чего-то не понимаю?