Разность квадратов и нечётные числа — олимпиадная задача по математике

  Пусть  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ⁿ всех подмножеств).

Ответ задачи отсутствует