Задача 60594

Темы:    [ Рекуррентные соотношения (прочее) ] [ НОД и НОК. Взаимная простота ] [ Уравнения в целых числах ]

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

Условие

Пусть a₁, a₂, ... – такая последовательность ненулевых чисел, что  (a_m, a_n) = a_{(m, n)}  (m, n ≥ 1).

Докажите, что все обобщенные биномиальные коэффициенты     являются целыми числами.

Подсказка

Докажите, что    допускает представление в виде линейной комбинации с целыми коэффициентами чисел    и  

Решение

  Число  (a_k, a_n–k) = a_{(k, n–k)} = a_(k,n) = (a_k, a_n)  является делителем числа a_n. Поэтому уравнение  xa_k + ya_n–k = a_n  имеет решение в целых числах (см. задачу 60489).
  Если  (u_n,k, v_n,k) – одно из этих решений, то  
  Поскольку числа    и    – целые, отсюда следует, что и все числа    – целые.

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

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	3
Название	Алгоритм Евклида и основная теорема арифметики
Тема	Алгебра и арифметика
параграф
Номер	4
Название	О том, как размножаются кролики
Тема	Классическая комбинаторика
задача
Номер	03.142