Делимость и ее свойство.

[KiberMath]

Lion
Расскажи пожалуйста по подробне про эту теорему. Очень бы хотелось увидеть ее доказательство

Dan_Te
ОТА известа )) Хорошое у тебя вышло доказательство

[bot]

RIP писал(а):

ОТА легко доказать и без этого свойства. Например, по индукции.

Каким образом? Так или иначе в доказательстве (как верно заметил Lion) будет присутствовать свойство Z, что это кольцо главных идеалов, отсюда линейное представление наибольшего общего делителя, а из него вытекает сабжевое свойство, которое в доказательстве ОТА по индукции используется.

[xolms]

KiberMath
c уменьшается и когда-то(когда переберем все простые делители) станет 1. Но r_1 делили на те же делители, а значит r1 кратно их произведению, то есть c
Помню доказывали ОТА с "самого начала", то есть без использования следствий и свойств появившихся после неё. Это было довольно долго и иногда раздражало то, что доказываем очевидные для нас факты.

[RIP]

bot писал(а):

RIP писал(а):

ОТА легко доказать и без этого свойства. Например, по индукции.

Каким образом? Так или иначе в доказательстве (как верно заметил Lion) будет присутствовать свойство Z, что это кольцо главных идеалов, отсюда линейное представление наибольшего общего делителя, а из него вытекает сабжевое свойство, которое в доказательстве ОТА по индукции используется.

Во-первых, нетривиальным в ОТА является только единственность разложения. Её и будем доказывать. От противного. Пусть $n=p_1p_2\ldots p_k=q_1\ldots q_l$ - наименьшее натуральное число, не обладающее свойством единственности разложения. Пусть $p_1$ - наим. из участвующих простых. Разделим все $q$ на него с остатком: $q_j=a_jp_1+r_j$. Перемножим эти равенства, в итоге получим нечто вроде $p_1m=r_1\ldots r_l$, $m\in\mathbb{N}$. Разложим левую и правую часть любым пособом на простые. Тогда слева будет присутствовать $p_1$, а справа нет. А это число меньше, чем $n$, т.к. $r_j<p_1<q_j$.

[bot]

Хм, действительно объехать можно - недосказанности типа "$a_j=0$ для некоторых j" очевидны.

Если не останавливаться на вопросе, стоит ли объезжать, то остаётся только это: без сложения не обойтись.

[KiberMath]

bot
А о каком сложении идет речь? У меня все получилось объехать и достаточно компактно и красиво.

Как уже говорил RIP интересно здесь только доказательство единственности...
В индукционном шаге предположили, что при n (произвольное число больше 2) каждое число k удовлетворяющее неравенству 2<=k<=n, можно представить в виде призведения простых чисел, и притом только одним способом...

Допустим, что n+1 представленно в виде произведения простых чисел

p_1*...*p_l = q_1*...*q_l
Докажем от противного, что одно из чисел q_i равно p_1.
Разделим q_i на p_1 В результате получиться q_i = p_1*k_i + r_i и в соответствии с этим перепишем произведение q_1*...*q_l Должна получиться вот такая абра кодабра

(p_1*k_1 + r_1)*...*(p_1*k_l + r_l)

Расскрыв скобки получим, что из всех слогаемых может делиться, а может и не делиться только одно, которое имеет вид

r_1*...*r_l

Но оно не делиться на p_1 !
Потому, что например r_1 < p_1<(n+1) откуда немедленно вываливаеться, что r_1 можно разложить на простые множители, и в этом разложении нет простого числа p_1. Аналогичная ситуация складываеться и с остальными r_i. И тогда получаеться что во всем этом большой произведении r_1*...*r_l
Нет простого числа p_1, а значит все это большое произведение не делиться на p_1. А вот это-то и противоречит тому, что по условию n+1 = p_1*...*p_l должно делиться на p_1


Но опять есть небольшая непонятка
Тут вроде все похоже. Вот только интересно было бы доказать строго тот факт, что при расскрытии скобок в (p_1*k_1 + r_1)*...*(p_1*k_l + r_l) единственным "сомнительным"(может делиться на p_1, а может и не делиться... сразу непонятно) слогаемым являеться только r_1*...*r_l
а все остальные содержат p_1, ну соответственно на него и деляться...
Я затрудняюсь четко сформулировать условие этой теоремы, чтобы доказать ее по индукции Подскажите пожалуйста, как это можно сделать...

[bot]

KiberMath писал(а):

А о каком сложении идет речь? У меня все получилось объехать и достаточно компактно и красиво.

Не получилось. В доказательстве явно присутствует операция сложения, вот здесь:

Цитата:

Разделим q_i на p_1 В результате получиться q_i = p_1*k_i + r_i

Как заметил Гильберт а я повторил (у него был другой пример), в любом доказательстве единственность разложения на простые обязано использовать операцию сложения.
Если бы существовало доказательство без сложения, то мы бы его тут же могли применить к полугруппе по умножению чисел вида 3k+1 и получили бы, что число 100 разлагается на простые сомножители единственным образом, а это не так:
100=4*25=10*10, и числа 4,25,10 - простые в этой полугруппе, так как имеют в этой полугруппе ровно два делителя. Аналогично, в этой же полугруппе 220=10*22=4*55.
Существования хотя бы одного разложения в этой полугруппе доказывается по индукции или эквивалентный в соотвествующей аксиоматике принцип наименьшего: в любом непустом подмножестве N (а в частности и этой полугруппы) есть наименьший элемент. Операция сложения в этой части доказательства не нужна.

Ну а по поводу непонятки всё просто. Надо вспомнить, что означает, что число $b$ делится на $a$ или $a$ делит $b$. Это означает, что существует такое число $c$, для которого выполняется равенство $b=ac$.
Теперь, в док-ве RIPa, если $r_j=0$ для некоторого $j$, то $q_j=a_jp_1$, в равенстве двух разложений числа $n$ мы можем сократить на $p_1$ и получить неоднозначно разлагаемое число, меньшее, чем $n$. Если же все $r_j\ne0$, то раскрывая скобки справа по дистрибутивности мы получим там все слагаемые кроме одного, делящиеся на $p_1$. Перенесём эти слагаемые налево и получим равенство $p_1m=r_1r_2...r_l$, в левой части которого имеем явно присутствующий множитель $p_1$.
Ну и концовка дословно по RIPу: разложим $m$, а также все $r_j$ на простые множители и получим два различных разложения числа $p_1m$ на простые сомножители, так как так как $r_j<p_1$, и следовательно ни один из $p_j$ при разложении на простые не можем дать простой множитель $p_1$. Так как $p_1m<n$, то получаем противоречие с выбором n.