ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам | Поиск |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 34993
Темы:    [ Основная теорема арифметики. Разложение на простые сомножители ]
[ Разбиения на пары и группы; биекции ]
[ Классическая комбинаторика (прочее) ]
[ Теория множеств (прочее) ]
Сложность: 3
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

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


Подсказка

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


Решение

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

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

web-сайт
задача

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .