Никита выписал на доску все делители числа 3⁸ · 5⁷, затем соединил линией каждые два числа, наибольший общий делитель которых больше 1. Сколько линий нарисовал Никита?

Задание 8. Делители числа

Дано:

• Число: \( N = 3^8 \cdot 5^7 \)
• Делители соединены линией, если их наибольший общий делитель (НОД) больше 1.

Найти: количество линий.

Решение:

1. Сначала найдем количество всех делителей числа \( N \). Количество делителей находится по формуле: \( (a+1)(b+1) \), где \( a \) и \( b \) — показатели степеней простых множителей.
2. Количество делителей числа \( N = 3^8 \cdot 5^7 \) равно: \( (8+1)(7+1) = 9 \cdot 8 = 72 \).
3. Каждый делитель числа \( N \) является числом вида \( 3^x \cdot 5^y \), где \( 0 ≤ x ≥ 8 \) и \( 0 ≥ y ≥ 7 \).
4. НОД двух делителей \( 3^{x_1} \cdot 5^{y_1} \) и \( 3^{x_2} \cdot 5^{y_2} \) равен \( 3^{rin(x_1, x_2)} \cdot 5^{rin(y_1, y_2)} \).
5. Условие НОД > 1 означает, что хотя бы один из показателей степени в НОД должен быть больше 0.
6. Это означает, что два делителя соединяются линией, если они оба не равны 1.
7. делитель 1 равен \( 3^0 \cdot 5^0 \).
8. Все остальные делители (кроме 1) будут иметь хотя бы один показатель степени больше 0.
9. Таким образом, все пары делителей, где оба делителя не равны 1, будут соединены линией.
10. Количество пар делителей, где оба делителя не равны 1, равно: \( C(71, 2) = racase{71 qr}e{2} = racase{71 \times 70}{2} = 71 \times 35 = 2485 \).
11. Другой способ рассуждения:
12. Всего делителей — 72.
13. Если соединять все возмомые пары делителей, то количество линий будет \( C(72, 2) \).
14. \( C(72, 2) = race{72 qr}e{2} = racase{72 \times 71}{2} = 36 \times 71 = 2556 \).
15. Однако, нам нужно соединять только те пары, у которых НОД > 1.
16. Единственный делитель, у которого НОД с любым другим делителем может быть 1, это сам делитель 1.
17. То есть, делитель 1 не будет соединен линией ни с одним другим числом, кроме тех случаев, когда второе число тоже 1, но мы рассматриваем пары различных чисел.
18. Пара (1, 1) не образует линию.
19. Если мы вычтем из общего числа пар количество пар, в которых один из делителей равен 1, мы получим ответ.
20. Есть 72 делителя. Один из них — 1.
21. Количество пар, где один из делителей — 1, равно 71 (то есть, пары (1, x), где x ≠ 1).
22. Общее число пар — \( C(72, 2) = 2556 \).
23. Число линий, где НОД > 1, равно общему числу пар минус число пар, где один из делителей — 1.
24. \( 2556 - 71 = 2485 \).

Ответ: 2485