Задача 34993

Темы:    [ Основная теорема арифметики. Разложение на простые сомножители ] [ Разбиения на пары и группы; биекции ] [ Классическая комбинаторика (прочее) ] [ Теория множеств (прочее) ]

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

Условие

Докажите, что нечётное число, являющееся произведением n различных простых сомножителей, можно представить в виде разности квадратов двух натуральных чисел ровно 2^n–1 различными способами.

Подсказка

2^n–1 – это число способов разбить множество из n простых сомножителей на два подмножества.

Решение

  Пусть  m = p₁p₂...p_n,  где  p₁, p₂, ..., p_n  – различные нечётные простые числа. Будем решать уравнение  x² – y² = m  в натуральных числах. Это уравнение приводится к виду  (x – y)(x + y) = p₁p₂...p_n,  откуда следует, что сомножитель  x – y  есть произведение нескольких чисел (возможно ни одного, в этом случае  x – y = 1)  из набора  p₁, p₂, ..., p_n,  а сомножитель  x + y  есть произведение оставшихся чисел из этого набора. При этом сомножителю  x – y  соответствует меньшее произведение. Таким образом, каждому решению  (x, y)  соответствует разбиение множества из n чисел на два подмножества.
  Наоборот, пусть есть некоторое разбиение чисел  p₁, p₂, ..., p_n  на два подмножества. Обозначим через t и s  (t < s)  произведения чисел в этих подмножествах  (t ≠ s,  поскольку числа  p₁, p₂, ..., p_n  различны). Тогда найдётся единственная пара натуральных чисел     для которой  x – y = t  и  x + y  = s  (x и y натуральные, так как t и s нечётны).
  Итак, число представлений m в виде разности квадратов двух натуральных чисел равно числу способов разбить множество из n элементов на два подмножества, то есть 2^n–1 (в два раза меньше числа 2ⁿ всех подмножеств).

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

web-сайт

задача