Вычитать доказательство по элементарной теории чисел

[someniatko]

Прохожу книгу по элементарной теории чисел, второй раздел - "Unique Factorization". В конце раздела - теорема:

Если $e_i \geqslant 0$, $f_i \geqslant 0$, ($i = 1, 2, \dots, k$), $m = p_1^{e_1}p_2^{e_2} \dots p_k^{e_k}$, $n = p_1^{f_1}p_2^{f_2} \dots p_k^{f_k}$, то
$(m, n) = p_1^{\min(e_1, f_1)}p_2^{\min(e_2, f_2)} \cdots p_k^{\min(e_k, f_k)}$.

$(m, n)$ означает наибольший общий делитель двух целых чисел.

Теорему нам автор оставил без доказательства. Говорит что "you should have no trouble convincing yourself that it is true". Книга небольшого формата, поэтому логично. Но вызов принят! Я решил попробовать полностью доказать теорему, опираясь на теоремы и леммы, которые уже появлялись в книге. Я их здесь буду называть "фактами", а промежуточные утверждения - "леммами". Доказательство оказалась, как по мне, пока что сложнее всех, что я уже проходил в этой книжке .

А к публике просьба проверить мое доказательство на пробелы - не хочется просто убедить себя в том, что доказал, а действительно доказать.

Факты, которые были в книге, на которые я опираюсь:
Основная теорема арифметики.
Факт 1. Если $q_1, q_2, \dots, q_k$ - простые, а некоторое простое $p \mid q_1 q_2 \dots q_k$, то $\exists i : p = q_i$
Факт 2. Если $(a, b) = d$, то $\exists x, y \in \mathbb{Z} : ax + by = d$
Факт 3. Если $a \mid m$, $b \mid m$ и $(a, b) = 1$, то $ab \mid m$

Промежуточные леммы, которые мне пришлось доказать:
Лемма 1. Если $(a, b) = 1$ и $(a, c) = 1$, то $(a, bc) = 1$
Доказательство.
Рассмотрим $d : d \mid a, d \mid bc$, тогда по определению делимости $\exists k, l : a = kd, bc = ld$ (1).
Из Факта 2, $\exists x, y : ax + cy = 1$. Умножив обе части на $b$:
$abx + bcy = b$, теперь из (1) имеем
$kdbx + ldy = b$,
$d(kbx + ly) = b$.
Следовательно, $d \mid b$. Но также $d \mid a$, а значит по определению НОД, $d \leqslant (a, b) = 1$.
Итак, любой делитель $a$ и $bc$ меньше либо равен $1$, а $1$ является их общем делителем, следовательно по определению $(a, bc) = 1$, чтд.

Лемма 2. Если $(a, b_1) = 1$, $(a, b_2) = 1$, ... , $(a, b_n) = 1$, то $(a, b_1 b_2 \cdots b_n) = 1$.
Доказательство.
Утверждение верно для $n = 1$, а для $n = 2$ доказано в Лемме 1.
Пусть оно верно для всех $n \leqslant k$. Тогда $(a, b_1 b_2 \cdots b_k) = 1$
Рассмотрим $n = k + 1$.
По условию, $(a, b_{k+1}) = 1$.
Из Леммы 1, $(a, (b_1 b_2 \cdots b_k) b_{k+1}) = 1$, раскрываем скобки из-за ассоциативности умножения, и получаем то, чтд.

Лемма 3. Если $a_1 \mid m, a_2 \mid m, \dots, a_n \mid m$, $\forall i, j \in \{1, 2, \dots, n\}, i \ne j, (a_i, a_j) = 1$, то $a_1 a_2 \cdots a_n \mid m$.
Утверждение верно для $n = 1$, а для $n = 2$ доказано в Факте 3.
Пусть оно верно для всех $n \leqslant k$. Рассмотрим $n = k + 1$.
Из условия, $(a_{k+1}, a_1) = 1, (a_{k+1}, a_2) = 1, \dots, (a_{k+1}, a_k) = 1$ и тогда из Леммы 2, $(a_{k+1}, a_1 a_2 \cdots a_k) = 1$.
Поскольку из условия $a_{k+1} \mid m$, а из предположения $a_1 a_2 \cdots a_k \mid m$, то из Факта 3, $(a_1 a_2 \cdots a_k)a_{k+1} \mid m$, и из ассоциативности умножения, чтд.

Фух, пока что я даже не дошел до самой теоремы! Если есть косяки уже в леммах, пишите. В следующих сообщениях напишу уже само доказательство.

[KhAl]

Ощущение, будто Вы передоказываете основную теорему арифметики. А можно решить совсем просто, если сразу использовать ОТА и определение делимости.

-- 21.07.2023, 20:30 --

Леммы доказаны верно.

[someniatko]

Итак, доказательство.

Факт 4. Если простое $p \mid ab$, то $p \mid a$ или $p \mid b$.

Сначала частный случай, когда $\forall i \in \{1, 2, \dots , k\}, e_i = 0$ (либо, полностью аналогично, $\forall f_i = 0$).
Тогда $(m, n) = 1 = p_1^0 p_2^0 \cdots p_k^0$
В таком случае учитывая условие теоремы ($\forall i, e_i \geqslant 0, f_i \geqslant 0$) получаем $\forall i, \min(e_i, f_i) = 0$.
Т.е. $(m, n) = 1 = p_1^0 p_2^0 \cdots p_k^0 = p_1^{\min(e_1, f_1)} \cdots p_k^{\min(e_k, f_k)}$, что удовлетворяет теореме.
Далее рассматриваем случай, когда $\exists i : e_i \geqslant 1$ и $\exists j : f_j \geqslant 1$.

Рассмотрим произвольное $c : c \mid m, c \mid n$ (общий делитель).
Рассмотрим простое число $q$ такое, что $q \mid c$. Тогда по транзитивности делимости $q \mid m$. Поскольку $m$ - произведение простых чисел, из Факта 1 следует что $q$ равно одному из простых $p_1, p_2, \dots, p_k$. Следовательно, число $c$ не имеет других простых делителей кроме $p_1, p_2, \dots, p_k$ и имеет вид $p_1^{g_1} p_2^{g_2} \cdots p_k^{g_k}$, где $\forall g_i \geqslant 0$.

Рассмотрим число $d = p_1^{\min(e_1, f_1)} p_2^{\min(e_2, f_2)} \cdots p_k^{\min(e_k, f_k)}$.
Поскольку для любых разных $i, j$, $\forall k, l \in \mathbb{Z}, (p_i^k, p_j^l) = 1$
$\forall i, p_i^{\min(e_i, f_i)} \mid p_i^{e_i}, p_i^{\min(e_i, f_i)} \mid p_i^{f_i}$, то применяя Лемму 3, заключаем что
$d \mid m$ и $d \mid n$. Т.е. $d$ является общим делителем $m$ и $n$.

Рассмотрим такое число $c$, что $\exists i : g_i > \min(e_i, f_i)$. Тогда либо $g_i > e_i$, либо $g_i > f_i$.
Пусть, например, $g_i > e_i$. Тогда $\exists l : c = p_i^{g_i} l = p_i^{e_i} p_i^{g_i - e_i} l$, причем $(p_i, l) = 1$. Также $\exists s : m = p_i^{e_i} s$, $(p_i, s) = 1$. Поскольку $p_i^{g_i} > p_i^{e_i}$, $p_i^{g_i} \nmid p_i^{e_i}$. Поскольку также $p_i \nmid s$, из Факта 4, который я изначально забыл указать и добавил здесь выше, $p_i^{g_i} \nmid m$ (поскольку если бы делило, то должно было бы делить $s$ или $p_i^{e_i}$). Но поскольку $p_i^{g_i} \mid c$, $c \mid m$, то $p_i^{g_i} \mid m$, противоречие. Аналогично если $g_i > f_i$.

Следовательно, $\forall i : g_i \leqslant \min(e_i, f_i)$ для любого числа $c$ указанного выше вида. Тогда $\forall c : c \mid m, c \mid n, c \leqslant p_1^{\min(e_1, f_1)} p_2^{\min(e_2, f_2)} \cdots p_k^{\min(e_k, f_k)} = d$, что по определению доказывает что $d = (m, n)$. Чтд.

Цитата:

Ощущение, будто Вы передоказываете основную теорему арифметики.

То-то я ее ни разу не использовал

Цитата:

А можно решить совсем просто, если сразу использовать ОТА и определение делимости.

Буду очень благодарен за текст доказательства.

[KhAl]

Прежде чем что-то доказывать, нужно подумать, как доказать утверждение наиболее просто.

someniatko в сообщении #1601954 писал(а):

Рассмотрим число $d = p_1^{\min(e_1, f_1)} p_2^{\min(e_2, f_2)} \cdots p_k^{\min(e_k, f_k)}$.
Поскольку для любых разных $i, j$, $\forall k, l \in \mathbb{Z}, (p_i^k, p_j^l) = 1$
$\forall i, p_i^{\min(e_i, f_i)} \mid p_i^{e_i}, p_i^{\min(e_i, f_i)} \mid p_i^{f_i}$, то применяя Лемму 3, заключаем что
$d \mid m$ и $d \mid n$. Т.е. $d$ является общим делителем $m$ и $n$.

Очень сложно. Докажите этот факт ($d \mid m$, $d \mid n$), не используя ничего, кроме определения делимости.

Цитата:

Рассмотрим произвольное $c : c \mid m, c \mid n$ (общий делитель).
Рассмотрим простое число $q$ такое, что $q \mid c$. Тогда по транзитивности делимости $q \mid m$. Поскольку $m$ - произведение простых чисел, из Факта 1 следует что $q$ равно одному из простых $p_1, p_2, \dots, p_k$. Следовательно, число $c$ не имеет других простых делителей кроме $p_1, p_2, \dots, p_k$ и имеет вид $p_1^{g_1} p_2^{g_2} \cdots p_k^{g_k}$, где $\forall g_i \geqslant 0$.

Правильно.

Цитата:

Следовательно, $\forall i : g_i \leqslant \min(e_i, f_i)$ для любого числа $c$ указанного выше вида.

Пусть $m = cr$, $n = cs$. Что получится, если применить к $c, r, s$ основную теорему арифметики?

[someniatko]

KhAl в сообщении #1601959 писал(а):

Очень сложно. Докажите этот факт ($d \mid m$, $d \mid n$), не используя ничего, кроме определения делимости.

Ахах, здесь я конкретно протупил. Именно из-за этого момента пришлось доказывать цепочку из трёх лемм. Вроде бы и бессмысленная работа, но мне понравилось. В принципе, эти три леммы, наверное, можно где-то еще по ходу дела использовать.

Т.к. $\forall i, e^i - \min(e_i, f_i) \geqslant 0$,
$m = (p_1^{\min(e_1, f_1)} p_1^{e_1 - \min(e_1, f_1)}) \cdots (p_k^{\min(e_k, f_k)} p_k^{e_k - \min(e_k, f_k)}) =$
$= (p_1^{\min(e_1, f_1)} \cdots p_k^{\min(e_k, f_k)})(p_1^{e_1 - \min(e_1, f_1)} \cdots p_k^{e_k - \min(e_k, f_k)}) =$
$= d(p_1^{e_1 - \min(e_1, f_1)} \cdots p_k^{e_k - \min(e_k, f_k)})$,
из чего $d \mid m$.

Заменим в формулах $e_i$ на $f_i$, $m$ на $n$, и получим что $d \mid n$.

-- 21.07.2023, 23:46 --

KhAl в сообщении #1601959 писал(а):

Пусть $m = cr$, $n = cs$. Что получится, если применить к $c, r, s$ основную теорему арифметики?

Я так понимаю, смысл такой: т.к. $r \mid m$, то аналогично тому как доказано выше для $c$, $r = p_1^{h_1} p_2^{h_2} \cdots p_k^{h_k}$.
Тогда $m = (p_1^{g_1} p_2^{g_2} \cdots p_k^{g_k}) (p_1^{h_1} p_2^{h_2} \cdots p_k^{h_k}) = p_1^{g_1 + h_1} p_2^{g_2 + h_2} \cdots p_k^{g_k + h_k} = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$
($\forall i, g_i \geqslant 0, h_i \geqslant 0$).

Пусть $\exists i : g_i > e_i$, тогда $g_i + h_i > e_i$. В разложение $m$ на простые множители, с одной стороны, будет входить $e_i$ множителей $p_i$, а с другой стороны - $g_i + h_i$ множителей, что противоречит Основной теореме арифметики.

Согласен, этот момент использование ОТА немного упрощает. Хотя и не так существенно, как замена моей конструкции выше на использование определения делимости. Спасибо за помощь!

[someniatko]

Нашел, кстати, пробел в исходном доказательстве.

Цитата:

Поскольку для любых разных $i, j$, $\forall k, l \in \mathbb{Z}, (p_i^k, p_j^l) = 1$

Во-первых, опечатка, не $k, l \in \mathbb{Z}$, а $k, l\in \mathbb{N}$, а во-вторых, этот факт тоже нужно доказать.

Итак, пусть $p, q$ - разные простые числа. Пусть $d$ суть их общий делитель.
Предположим что $d > 1$. Тогда из еще одного факта, который был в книге, $\exists r : r \mid d$, где $r$ простое.
$r \mid d, d \mid p^k \Rightarrow r \mid p^k$. Из Факта 1, $r = p$. Тогда $p \mid d$.
Т.к. $d \mid q^l$, $p \mid q^l$. Из Факта 1, $p = q$. Противоречие, предположение неверно, и $d \leqslant 1$.
Из того что $1$ является общим делителем любых двух натуральных, он и есть $(p^k, p^l)$ по определению.

[KhAl]

someniatko, попробую пофилософствовать...

Мне нравится Ваша тяга к строгости и умение самостоятельно думать. Вы молодец

Но здесь Вы слишком подробно изучаете текст книги. Запоминать следует только основное: из теорем -- только самые полезные и мощные; из доказательств запоминать основные идеи, и уметь по ним восстанавливать полные доказательства (простые и прямолинейные доказательства лучше вообще не помнить). Из приведённых Вами фактов я бы запомнил ОТА и Факт 2, а остальное выкинул нафиг (память конечна, раз; будет каша в голове, два).

Автор книги предполагал следующий план решения:
1. Пусть для двух натуральных чисел $a$ и $b$ заданы их разложения на простые множители. Сформулировать в терминах этих разложений, когда $a \mid b$. Доказать с помощью ОТА.
2. Воспользоваться 1.

И вообще, после пункта 1 (и на базе Вашей задачи) утверждения фактов 1, 3, 4 и лемм 1, 2, 3 переходят в разряд очевидных, их доказательства можно прокрутить в голове (Здесь есть небольшое жульничество, потому что лемма 1 сама по себе участвует в доказательстве ОТА. Но этот вопрос важен только когда Вы пытаетесь доказать ОТА)

Так же, не нужно воспринимать

Цитата:

Тогда из еще одного факта, который был в книге, $\exists r : r \mid d$, где $r$ простое.

как "ещё один факт, который был в книге". Это просто утверждение, которое независимо от всяких книг приходит в голову и на одном дыхании доказывается (в уме). Вы просто натыкаетесь на него, думаете чуть-чуть, почему оно верно (ОТА тут не причём, если что! нужно уметь доказывать на основе базовых свойств делимости) и... не записываете его доказательство, потому что любой человек, который читал док-во ОТА и понял его, способен провести те же рассуждения. В худшем случае Вас спросят -- "а почему вот это вот верно?", и Вы без проблем ответите (либо поймёте, что утверждение не так очевидно, как Вам казалось -- тоже бывает).

В общем. Советую в голове прокрутить мой пункт 1 (выше) -- не просто доказать утверждение, но понять, почему оно правда очевидно.

[wrest]

someniatko в сообщении #1602177 писал(а):

Итак, пусть $p, q$ - разные простые числа. Пусть $d$ суть их общий делитель.
Предположим что $d > 1$.

Э... у простых чисел же только два делителя: единица и само число просто по определению простого числа. Так что, поскольку $p \ne q$, сразу следует $d=\{1,p\} \bigcap \{1,q\}=\{1\}$

[KhAl]

wrest ну очевидно, он забыл степени поставить... это важно?

-- 23.07.2023, 22:25 --

А вот то, что $d \in \{1,\, p,\, p^2,\, \dots,\, p^{k}\} \cap \{1,\, q,\, q^2,\, \dots,\, q^{l}\} = \{1\}$ это да, это надо понимать.

[someniatko]

KhAl в сообщении #1602222 писал(а):

Мне нравится Ваша тяга к строгости и умение самостоятельно думать. Вы молодец

Спасибо

KhAl в сообщении #1602222 писал(а):

Но здесь Вы слишком подробно изучаете текст книги. Запоминать следует только основное: из теорем -- только самые полезные и мощные; из доказательств запоминать основные идеи, и уметь по ним восстанавливать полные доказательства (простые и прямолинейные доказательства лучше вообще не помнить).

Мне просто нравится заполнять подобные слепые пятна. Также я создаю себе "челленж" что уж если доказывать, то исключительно опираясь на те факты, которые я "официально" прошел. Наверное, я здесь ради процесса, а не конечного результата . А проблем с тем, чтобы что-то забыть у меня нет - я уже забыл некоторые леммы прошлого раздела, постоянно приходилось активно листать во время решения задачи топика, в поисках чего-то подходящего.

KhAl в сообщении #1602222 писал(а):

Автор книги предполагал следующий план решения:
1. Пусть для двух натуральных чисел $a$ и $b$ заданы их разложения на простые множители. Сформулировать в терминах этих разложений, когда $a \mid b$. Доказать с помощью ОТА.
2. Воспользоваться 1.

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

KhAl в сообщении #1602222 писал(а):

И вообще, после пункта 1 (и на базе Вашей задачи) утверждения фактов 1, 3, 4 и лемм 1, 2, 3 переходят в разряд очевидных, их доказательства можно прокрутить в голове (Здесь есть небольшое жульничество, потому что лемма 1 сама по себе участвует в доказательстве ОТА. Но этот вопрос важен только когда Вы пытаетесь доказать ОТА)

В этом разделе автор приводит пример числовой системы, где некоторые леммы (из книги, не мои), ведущие в итоге к доказательству ОТА, верны, но сама ОТА неверна, и в какой-то момент доказательство начинает ломаться. Что собственно еще больше подогрело интерес к строгости доказывания. И из лемм таким образом становится труднее выделить самые "мощные и важные", потому что внезапно в некотором смысле важной в этом контексте становится та, на которой доказательство сломалось - и интересны те свойства, на которую она опиралась. Это уже наверное предмет абстрактной алгебры.

wrest, да, я упустил что $d$ - общий делитель $p^k$, $q^l$, а не просто $p$ и $q$.

Цитата:

А вот то, что $d \in \{1,\, p,\, p^2,\, \dots,\, p^{k}\} \cap \{1,\, q,\, q^2,\, \dots,\, q^{l}\} = \{1\}$ это да, это надо понимать.

Ну снова же, для меня, как и для вас, это совершенно очевидно. А вот как дело доходит до формального доказательства...