Сколько несократимых правильных дробей со знаменателем 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.