Прикалываетесь.

Отнюдь.

Хорошо. Мысленные образные манипуляции.

Х не делится на Р. То есть остается остаток, меньший чем Р. (Деление можно представить серией вычитаний, да?)

Теперь если У делится на Р, то на Р будет делится любое произведение У*К, при любом целом К.
Значит, если У делится на Р, то и (неделимое) Х умноженное на У, станет делиться на Р. Произведение
У*Х будет делиться на Р.

Но нам дано что У тоже не делится на Р. Как понять, что Х*У не станет делиться на Р никогда?

Упростим то, что видим. Из Х отдельно вычитаем сколько надо раз Р, пока не останется остаток, меньший чем Р, назовем его Ох. То же самое сделаем с У, пока не останется остаток Оу. То есть делимую часть мы убрали, убрали то, что абсолютно ясно делится и оставили два остатка.

Если Ох*Оу не делится на Р, то утверждение доказано. Пока мы знаем, что оба сомножителя - целые и меньшие, чем Р.

Но нам дано, что Р - простое. То есть не раскладывается на множители кроме единицы и самого себя. Нет двух чисел, меньших чем Р, произведение которых равно Р. Это если наши остатки Ох и Оу малы и их произведение меньше чем Р. Они никогда не дадут в произведении Р. Это ясно.

Остается понять последнюю тему - а вдруг оба остатка достаточно велики, оба чуть меньше Р. И их произведение будет больше чем Р. Вдруг произведние поделится на Р? Тогда все пропало.

Не поделится. Потому что. Предположим, что поделится. И, например, Ох*Оу = 2*Р. Тогда мы можем на два разделить обе части и получим слева произведение двух чисел, дающих Р. А таких нет.

Ну в общем все же ясно?

С чего бы это хотя бы одно из Ox или Oy делилось на 2?

Не понял вопроса.

"Тогда мы можем на два разделить обе части и получим слева произведение двух чисел, дающих Р."

Почему мы получим произведение двух чисел слева? А если справа будет не 2 на P, а K на P? Не пользуетесь ли Вы здесь утверждением теоремы, которую доказываете?

Мне кажется что не пользуюсь.

У нас тождество. То есть просто мы видим

А = Б * С;

где А - какое-то число, Б - другое какое-то число, а С - неизвесная переменная. Как найти С? Как всегда: С = А/Б.

Или еще раз другии словами. Поделится произведение остатков на Р? И доказываем от противного.

Вы делите Ox*Oy на 2. Почему результат будет произведением двух чисел? Ровно по той теореме, что доказывается, хотя бы одно из чисел Ox или Oy делится на 2. Без ограничения общности можно предположить, что это Ox, а значит P=(Ox/2)*Oy. Теперь, чтобы получить противоречие, еще надо заметить, что Ox/2 отлично от 1, но это мелочи. Не мелочь, то что пришлось воспользоваться доказываемой теоремой. Конечно, для P=2 утверждение теоремы очевидно. А что будет если множитель при P будет отличен от 2?

Да, кто-то из нас прав. А кто-то нет :)

Как я все это вижу. Есть некое простое Р. Даже не важно, что простое, сейчас это не играет роли. Есть некое Р. Нашлись какие-то два числа, меньшие чем Р, произведение которых делится на Р. Можно изобразить:

А*Б = М*Р, А и Б - эти самые два числа, меньшие чем Р, а М - кратность, с которой делится это произведение.

Давайте просто их перемножим:

А*Б = "произведение"

Но у нас одновременно:

М*Р = "произведение"

("произведение" - это число, результат умножения А*Б или М*Р, все числа целые)

Скажите, мы можем утверждать, что "произведение" делится нацело на А, или на Б, или на М, или на Р?

Да, произведение делится нацело на А, на Б, на М и на Р. Но нам-то нужно, что Р делится на что-то отличное от 1 или Р. Внизу используется индукция по Р (в том смысле, что мы предполагаем, что утверждение доказано для всех простых меньших Р). Теперь мы знаем, что А больше чем М и меньше чем Р. Мы можем записать А как произведение простых Р1, Р2, ..., Рн. Каждое из этих простых меньше Р, а значит к ним применимо доказываемое утверждение теоремы по индукции. Следовательно каждое из этих простых делит либо М либо Р. Если хотя бы одно из них делит Р, то мы получаем противоречие, так как все Р1, Р2, ..., Рн меньше Р и Р простое. Значит все Р1,...,Рн делят М нацело. Пусть А"=Р2*...*Рн и М"=М/Р1. Тогда А"*Б=М"*Р, причем М" строго меньшу чем А. К этому равенству применимо тоже рассуждение что и раньше. Следовательно, можно поделить на Р2, и так далее. В конце концов, получим равенство Рн*Б=М"""""*Р с Рн простым, строго больше чем М""""" и одновременно делящим нацело это мифическое М""""". Такого М""""" в природе существовать не может. Получили противоречие.

Вот ниже как раз и подтвердили, мне кажется:

http://flaass.livejournal.com/505407.html?thread=3024703#t3024703

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

"х и у взаимно просты" надо определять как "хК+уК=К".
То есть, вплоть до этого момента никакие нормы не нужны, и даже единица не нужна.
А потом вдруг все разом требуется (деление с остатком, вроде, без нормы не определить?). Загадочно...

вообще-то я не алгебраист, то что я помню - это из общих мат-меховских курсов.

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

Насколько я смутно помню, нам Яковлев доказывал это даже в таком ключе:
Если кольцо - ОГИ, то в нем выполняется ОТА.
Самый жирный и понятный класс ОГИ - это нормированные кольца с делением с остатком.
Бывают кольца, которые ОГИ, но без деления с остатком, но это сложные извращения.

А вот про то, является ли ОГИ необходимым, а не только достаточным, условием для ОТА, я не помню.

Бывают кольца, которые ОГИ, но без деления с остатком, но это сложные извращения.
как тут уже ниже сказали, это совсем не извращения.

Ниже сказали совсем другое: что из ОТА ГИ не следует.:)

та я уж понял, что везде облажался.

> Даже с таким определением взаимной простоты мне непонятно, как доказать, что неприводимый элемент взаимно прост с любым другим, не делящимся на него.
Ага, тут и проблема.
Индукционная лемма при таком определении, если в К есть единица, доказывается в две строчки.
А вот для базы доказать, что разные простые взаимно просты, тут и нужно деление с остатком.

"примеры колец, где ОТА выполняется, а вот деления с остатком (и вместе с ним алгоритма Евклида и НОД с его лин.представлением) нету" - все кольца многочленов от >1 переменной.:) Кстати, ГИ (линейное представление НОД) слабее евклидовости.:)

Во, пришел алгебраист и все объяснил.
А то я уже ничего не помню.

но ведь кольцо многочленов с >1 переменной - это ОГИ? То, что это слабее евклидовости, я понимаю.

Нет, не ГИ никаким боком.:)

Ох. сложная наука алгебра.

ГИ - это размерность 1. Тебя удивляет, что размерность плоскости больше?:)

И, естественно, из евклидовости все следует (если нет делителей ноля).

существуют а и в c d
xa=pb+1
yc=pd+1
---------
далее перемножаем

+1.

Ну, это по сути линейное представление НОД.

А кто бы сомневался?:)

Можно ей не пользоваться (явным образом), ограничиваясь одним делением с остатком. Нам так доказывали в 6 классе.

Выберем наименьшее простое p такое, что для каких-то x,y произведение xy делится на p, а x и y не делятся. Можно заменить x,y на их остатки по модулю p. Так что не умаляя общности x,y<p. Но тогда у x есть простой делитель, меньший p, на который делится p*1, но не делится ни p, ни 1. Противоречие.

Да, кстати, есть и такой вариант. Помнится, будучи в 5м (по нынешнему счету - в 6м) я как раз его и придумал.:)

Ага, единица все сразу делает.
А если ее нет?

А что есть?:) Для кольца четных чисел, например, однозначности разложения нет совсем.:)

Ага, это у меня модельный пример, когда все плохо.
Кстати, хороший вопрос на засыпку.

есть популярная идея, что НА САМОМ ДЕЛЕ ее понять невозможно не доказав гипотезу Римана.

или вас не миллион интересовал? :)

извиняюсь за лишнее дилетантство:
в натуральном ряду, как в таком (http://bntr.planet.ee/lj/StructureOfSequence.gif) многомерном паралеллепипеде,
произведением оказывается сумма векторов, которая не может иметь отсутствующей у слагаемых координаты.

Красивая картинка. Ее и доказываем. А главное - выясняем, в каких еще ситуациях удастся доказать то же самое.