"Транзитивные числа"

[Odysseus]

После ответа в теме Красота математической формулы я стал вспоминать, что мне еще понравилось в математике, и вспомнил определение, которое когда-то придумал :) Я тогда учил начала теории чисел и обращал внимание на идеи и приемы, которые объединяют разные доказательства.

Одним из универсальных приемов было поделить большее положительное число на меньшее и посмотреть на свойства остатка. Если меньшее число и остаток обладали каким-то общим свойством, и при этом меньшее число было наименьшим положительным целым числом обладающим этим свойством, то можно было заключить, что остаток равен нулю. Такой прием использовался во многих доказательствах, поэтому я придумал следующее определение:

Определение
Упорядоченная пара целых чисел $(a, b)$ называется транзитивной относительно свойства $P$, если
1) $|a| \geq |b|$
2) $b$ и остаток от деления $\frac{a}{b}$ удовлетворяют $P$.

Термин "транзитивность" в определении выбран из-за того, что свойство $b$ "переносится" затем на остаток от деления $\frac{a}{b}$. Возможно это не лучший термин для данного определения (может путать с бинарным отношением транзитивности), но лучше подобрать не удалось. Например, "сравнимые по свойству..." может еще больше путать, поскольку будет вызывать аналогии со сравнимостью по модулю. Да и вообще, в математике практически все понятные термины уже за чем-то закреплены :), а какую-то ассоциацию с "переносом свойства" проиллюстрировать хотелось.

Для краткости я далее слова "упорядоченная пара" опускаю, и называю числа $a$ и $b$ транзитивными в том порядке, в котором они стоит в этой паре.

Отсюда следует лемма, которая является стандартной идеей в некоторых теоремах элементарной теории чисел.

Лемма
Если $a$ и $b$ транзитивные относительно свойства $P$, и $b$ - наименьшее положительное целое число удовлетворяющее $P$, то $b|a$.
Доказательство: делим $a$ на $b$ с остатком, последний удовлетворяет $P$ согласно транзитивности $a$ и $b$, но при этом меньше $b$, значит остаток равен нулю.

Главной содержательной частью для меня здесь было определение транзитивности чисел, поскольку последующая лемма уже очевидна. Т.е. более интересным был не прием из леммы, а то, что некоторые теоремы следуют из транзитивности чисел относительного некоторого свойства, что помогало понять в чем эти теоремы близки друг другу. В итоге, схемы их доказательств были следующими:
- Найти свойство относительно которого некоторые числа являются транзитивными.
- Найти наименьшее положительное число удовлетворяющее этому свойству. Часто некое наименьшее число или уже было задано, или естественно проявляется. В таких случаях нахождение соответствующего свойства и проверка транзитивности становились проще.
- Применить лемму и посмотреть, что получается.

Примеры
Их можно расписать подробнее и формальнее, но я привожу хорошо известные факты, поэтому ограничусь только тем, как они интерпретируются в рамках данного определения.

1) Алгоритм Евклида.
Это не очень содержательный пример, но он полезен для иллюстрации простейшего применения транзитивности и последующей леммы.
Свойство $P$: "иметь те же общие делители, что общие делители чисел $a_1$ и $a_2$" (НОД которых мы ищем в процессе алгоритма Евклида, при этом полагаем $|a_1| \geq |a_2|$).
Транзитивные пары: $a_1, a_2$, затем $a_2, a_3$, и далее любые два числа $a_{n}, a_{n+1}$ при известном использовании алгоритма Евклида.
Лемма здесь приводит к известному факту, что предпоследнее число в этой цепочка делится на последний (наименьший положительный) остаток, который и является НОД для $a_1$ и $a_2$

2) Все кратные данного набора чисел делятся на НОК.
Свойство $P$: "быть кратным данного набора чисел".
Транзитивные пары: $a=$ любое из кратных, $b=$ НОК. А поскольку НОК это наименьшее положительное число удовлетворяющее $P$, то из леммы следует, что все кратные на него делятся.

3) НОД данного набора чисел можно представить в виде их линейной комбинации.
Свойство $P$: "быть представленным в виде линейной комбинации данных чисел".
Транзитивные пары: $a=$ любое из данных чисел, $b=$ наименьшее положительное значение их линейной комбинации.
Из леммы тогда следует, что $b$ будет делителем каждого из данных чисел, а значит и их НОД (поскольку оно также делит все общие делители данных чисел, как и любая другая линейная комбинация).

4) Любой идеал в кольце целых чисел является главным.
Свойство $P$: "принадлежать данному идеалу".
Транзитивные пары: $a=$ любое число из данного идеала, $b=$ наименьшее положительное число принадлежащее данному идеалу.
Из леммы следует, что $b$ будет делить каждое число из идеала, а значит идеал будет порождаться $b$, т.е. будет главным. (Фактически, здесь доказывается то же, что в №3 выше.)

5) Если ни $a$, ни $b$ не делятся на простое число $p$, то и произведение $ab$ не делится на $p$.
Обычно доказывается более общее утверждение (если $p|ab$, и $(p,b)=1$, то $p|a$), но для краткости ограничусь данной версией. Кроме того, ее достаточно для доказательства единственности разложения на простые множители, и все остальное будет уже следовать из последнего.

Есть несколько вариантов доказательства, но наиболее подходящим для наших целей является доказательство из "Трудов по теории чисел" Гаусса (стр. 21-22, рекомендую его посмотреть). Это доказательство мне и в принципе нравится больше остальных. Остальные доказательства не менее простые, но в этом, как мне кажется, понятнее "почему" так происходит. (Конечно, наиболее ясно это после использования единственности разложения числа на простые множители, но последнее, проще всего, доказывается как раз на основе данного утверждения.)

- Сначала сводим это утверждение к следующему: если положительные $a$ и $b$ меньше простого числа $p$, то произведение $ab$ не делится на $p$. Это, очевидно, равноценное утверждение, поскольку при сравнении $ab\equiv 0(\mathrm{mod}p)$ всегда можно перейти к наименьшим положительным вычетам для $a$ и $b$.
- Доказываем от противного, т.е. предположим $ab\equiv 0(\mathrm{mod}p)$. При этом можно считать, что $b$ это наименьшее положительное число удовлетворяющее этому свойству (если нет, то всегда можно выбрать меньшее). Также очевидно, что $b>1$, иначе $a=p$
- Свойство ${P}$: "при умножении числа на $a$ произведение должно делитьcя на $p$". Транзитивная пара: $p$ и $b$, поскольку при делении $p$ на $b$ c остатком у нас получится $p-kb$ для некоторого $k$. А поскольку $b$ это наименьшее число удовлетворяющее свойству $P$, то $p|b$, что невозможно, значит предположение $ab\equiv 0(\mathrm{mod}p)$ было неверным.

--

Получилось довольно много слов, но фактически это одно и то же, и голове одна и та же картинка. Возможно, это все банально, и, в лучшем случае, имеет ограниченную педагогическую ценность как одна из возможных картинок/аналогий в подобных доказательствах, поэтому далее я не продолжал. (Хотя можно было бы обобщить на произвольные евклидовы кольца и посмотреть где еще можно применить такую схему.) Тем не менее, может кому-то будет интересным, поэтому поделился.

Пара вопросов в конце:
1) Показалось ли это небанальным и интересным? :)
2) Встречали ли вы что-то похожее, пусть и в других контекстах и приложениях?

[kotenok gav]

Бесконечный спуск?

[Odysseus]

kotenok gav
Как я понимаю, вы отвечали на "2) Встречали ли вы что-то похожее, пусть и в других контекстах и приложениях?"

Конечно, некоторое пересечение и родство с методом бесконечного спуска здесь есть, поскольку в обоих случаях используется ограниченность снизу любого подмножества множества натуральных чисел. Это одно из базовых свойств натуральных чисел, которое является основной для многих утверждений в отношении объектов состоящих из целых чисел. Аналогично можно привести, например, свойство полноты вещественных чисел, которое является основой многих доказательств для объектов состоящих из вещественных чисел (введение арифметических операций для вещественных чисел, пределы последовательностей, непрерывные функции и т.д.).

Но это более глобальные картинки/аналогии, а было интересно если есть что-то близкое к данному более узкому свойству "транзитивности", которое проявляется в более ограниченном количестве структур/теорем, но объединяет их характерным образом.

[kotenok gav]

Нет, это и есть бесконечный спуск (точнее, поскольку бесконечный спуск невозможен, мы имеем что $b\mid a$).

[Odysseus]

Кажется, вы меня не вполне поняли. Я не говорил, что здесь нет бесконечного спуска. Идея из него, конечно, есть, поскольку в обоих случаях используется ограниченность снизу любого подмножества множества натуральных чисел, как я и написал. Очевидно, что всегда когда утверждается, что существует наименьшее натуральное число обладающее некоторым свойством, а потом из этого выводится нужное заключение, то можно сказать, что используется метод бесконечного спуска. Мой пойнт был в том, что бесконечный спуск это некое общее свойство/идеология, глобальная картинка или аналогия, но здесь используются также некоторые более узкие свойства и приемы.

Приводя опять же аналогию со свойством полноты вещественных чисел: это некое глобальное свойство, которое используется или подразумевается во многих доказательствах, но кроме него есть и другие идеи и приемы.

[beroal]

Odysseus в сообщении #1498689 писал(а):

3) НОД данного набора чисел можно представить в виде их линейной комбинации.

Доказательство этой теоремы исходит из существования НОД. А существование НОД, по крайней мере конструктивно, доказывается с помощью алгоритма Эвклида, который также даёт и линейную комбинацию. Так что эта теорема с моей точки зрения бесполезна…

[vicvolf]

Odysseus Может быть это можно обобщить и вместо транзитивных чисел взять транзитивное утверждение? Тогда у нас получаются метод математической индукции, бесконечного спуска и.т.д.