Question

Сколько существует правильных несократимых дробей, у которых числитель - целое положительное число, а знаменатель равен 8! (8 факториал)?

Answer 1

9216

Пошаговое объяснение:

Предположим, что существует несократимая дробь, наибольший общий делитель d числителя и знаменателя которой отличен от 1. Но тогда эту дробь можно сократить на d. Получили противоречие, а значит, числитель и знаменатель являются взаимно простыми. Поскольку у правильной дроби числитель меньше знаменателя, то для ответа на вопрос необходимо вычислить количество чисел, взаимно простых с 8! и не превышающих 8! Задача сводится к нахождению функции Эйлера φ от числа 8!

Воспользуемся свойством мультипликативности функции Эйлера:

если a и b  — взаимно простые, то  φ(ab) = φ(a)φ(b)

Замечу, что степени двух различных простых чисел (p_1)^α и (p_2)^β являются еще и взаимно простыми:

$p_1^\alpha \; \vdots \; p_1^0 (=1), \; p_1, \; p_1^2, \; p_1^3,..., p_1^{\alpha -1}, \;p_1^\alpha \\p_2^\beta \; \vdots \; p_2^0(=1), \; p_2, \; p_2^2, \; p_2^3,..., p_2^{\beta -1}, \;p_2^\beta$

(видно, что у (p_1)^α и (p_2)^β нет общих делителей, кроме 1)

Исходя из изложенного, если записать каноническое разложение 8! на простые множители:

8! = 8×7×6×5×4×3×2×1 = 2³×7×2×3×5×2²×3×2 = 2^7 × 3² × 5 × 7,

то станет целесообразно упростить решение: φ(8!) = φ(2^7)φ(3²)φ(5)φ(7)

А теперь приведу формулу для вычисления φ(p^α) (p — простое):

φ(p^α) = p^α - p^(α-1)

Если же α = 1, то:

φ(p) = p-1

Имеем:

φ(8!) = φ(2^7 × 3² × 5 × 7) = φ(2^7)φ(3²)φ(5)φ(7) = (2^7 - 2^6)(3² - 3)(5-1)(7-1) = 2^6(2-1) × 3(3-1) × 4 × 6 = 64×3×2×4×6 = 9216,

что и есть ответ на вопрос задачи.