Для нахождения значения функции Эйлера- дабы не ограничиваться разрядностью, будем использовать php gmp
Я приведу здесь две реализации, первая из которых "формальна" (понятнее но работает медленно), а вторая работает значительно быстрее:
