Задача 78014

Темы:    [ Четность и нечетность ] [ Функция Мебиуса ] [ Индукция (прочее) ] [ Основная теорема арифметики. Разложение на простые сомножители ]

Сложность: 4 Классы: 8,9,10

Условие

Дано число  H = 2·3·5·7·11·13·17·19·23·29·31·37  (произведение простых чисел). Пусть 1, 2, 3, 5, 6, 7, 10, 11, 13, 14, ..., H – все его делители, выписанные в порядке возрастания. Под рядом делителей выпишем ряд из единиц и минус единиц по следующему правилу: под единицей 1, под числом, которое разлагается на чётное число простых сомножителей, 1, и под числом, которое разлагается на нечётное число простых сомножителей, –1. Доказать, что сумма чисел полученного ряда равна 0.

Решение

  Будем называть "чётным" делитель, который разлагается на чётное число простых сомножителей (1 относится к "чётным" делителям), а "нечётным" – делитель, который разлагается на нечётное число простых сомножителей. Докажем индукцией по k, что число  N_k = 2·3·5·7·...·p_k  (произведение первых k простых чисел) имеет 2^k–1 "чётных" делителей и 2^k–1 "нечётных" делителей. (Тогда для числа N_k рассматриваемая сумма равна  2^k–1 – 2^k–1 = 0.)
  База. Для числа  N₁ = 2  утверждение очевидно.
  Шаг индукции. Число N_k+1 имеет 2^k–1 "чётных" делителей и 2^k–1 "нечётных" делителей, не делящихся на p_k+1 (все эти делители являются делителями числа N_k). Помимо этих делителей оно имеет делители, делящиеся на p_k+1. А именно, 2^k–1 "чётных" делителей, соответствующих "нечётным" делителям числа N_k, и 2^k–1 "нечётных" делителей, соответствующих "чётным" делителям числа N_k. В итоге получаем  2^k–1 + 2^{k– 1} = 2^k  "чётных" делителей и 2^k "нечётных" делителей.

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Номер	17
Год	1954
вариант
Класс	8
Тур	2
задача
Номер	3