Сколько несократимых правильных дробей со знаменателем 145

Задача: сколько несократимых правильных дробей со знаменателем 145? Ключ: для такого типа дробей количество равно числу натуральных чисел n, 1 ≤ n ≤ 144, которые не имеют общих делителей с 145 кроме единицы. То есть это φ(145) ( функция Эйлера φ). 1) Факторизация знаменателя: - 145 = 5 · 29, оба простые. 2) Способ 1 — через φ(145) (мультпликативность φ): - φ(145) = φ(5 · 29) = φ(5) · φ(29) = (5−1) · (29−1) = 4 · 28 = 112. 3) Способ 2 — через включение-исключение: - Считаем числа 1..144, не делящиеся на 5 и не делящиеся на 29. - Всего чисел: 144. - Множители 5: floor(144/5) = 28. - Множители 29: floor(144/29) = 4. - Множители одновременно 5 и 29 (рунг 145): floor(144/145) = 0. - Число допустимых n: 144 − 28 − 4 + 0 = 112. Ответ: 112. Дополнительно: - Обычно число несократимых дробей со знаменателем n равно φ(n). - Пример: φ(145) = 112, как рассчитано выше. - В случае 145=5·29 дроби 29/145, 58/145, 87/145, 116/145 и т.д. не являются несократимыми, так как имеют общие делители с 145. Только 112 из 144 возможных чисел n попадают в admissible.