Так значит, во второй задаче мы доказали существование разложения на простые.
На самом деле, единственность можно доказывать разными способами, например,
вы можете открыть Википедию и там будет такое, не очень сложное доказательство.
Вот я хочу привести доказательство, которое более хорошее в том смысле,
что оно обобщается на некоторые более общие структуры.
И вообще очень красивое.
Итак, значит нам нужно будет доказать сначала вспомогательное утверждение,
а потом мы докажем единственность.
Вспомогательное утверждение звучит так, это задача №3.
То есть, если у нас есть два числа a и b, натуральных,
и p – простое число,
[ПИШЕТ НА ДОСКЕ] Причем известно,
что произведение a и b делится на p.
А a не делится на p.
Но мы хотим доказать, что b делится на p.
Это наша цель.
Значит, мы будем доказывать его с помощью нескольких последовательных утверждений.
Сначала мы введем такое хитрое множество M, а именно,
это будет множество таких целых чисел, целых чисел x,
таких что ax делится на p.
Дальше мы хотим доказать про него несколько замечательных свойств.
Во-первых, заметим что, если у нас есть два числа, которые лежат в M,
то и их сумма лежит в M.
Действительно.
[ПИШЕТ НА ДОСКЕ] Значит,
что у нас значит, что xy лежит в M?
Это значит, что ax делится на p и ay делится на p.
Ну тогда и a ∙ (x + y) делится на p.
[ПИШЕТ НА ДОСКЕ] Ну и значит,
по определению x + y лежат в M.
Так, это у нас было первое свойство.
Второе свойство, что если x лежит в M,
домножить на какое-то произвольное целое число,
то их произведение также будет лежать в M.
[ПИШЕТ НА ДОСКЕ] Докажем это.
Ну действительно, если у нас x лежит в M,
тогда по определению, ax делится на p.
Ну тогда, если мы x умножим на z, то a ∙ (x ∙ z) — это то же самое,
что (a ∙ x) ∙ z, и это, конечно, тоже делится на p.
Поэтому, раз a ∙ (x ∙ z) делится на p,
то xz у нас тоже лежит в M.
Казалось бы, это какие-то простые свойства, которые непонятно к чему ведут.
Но давайте докажем еще более замечательные свойства.
Значит, пусть у нас есть два числа, которые лежат в M.
Тогда и остаток от деления одного числа на другое тоже будет лежать в множестве M.
[ПИШЕТ НА ДОСКЕ]
[ПИШЕТ НА ДОСКЕ]
[ПИШЕТ НА ДОСКЕ]
[ПИШЕТ НА ДОСКЕ] Вот,
не очень видно, я наверное здесь вмещусь, а потом перейду на ту доску.
Ну действительно, а что такое остаток от деления x на y?
Это такое число, которое представляется...
Значит, мы хотим развить x на y, значит y = x ∙ q + r.
Но это то же самое, что написать
r представить можно, как x − y ∙ q.
А теперь смотрите.
По второму свойству, y лежит в M и значит, y ∙ q лежит в M.
Ну или, y ∙ (−q) лежит в M.
А по первому свойству, сумма двух элементов из M лежит в M.
Значит, x − y ∙ q лежит в M.
Так, ага, значит мы доказали, что если два числа лежат в M,
то и остаток от деления одного числа на другое тоже лежит в M.
Ну тоже, в общем, не очень понятно, зачем это свойство нужно.
Давайте теперь его очень хитро применим.
А именно,
рассмотрим минимальное натуральное число, которое лежит в множестве M.
Пусть, так,
давайте какое-нибудь придумаем число, ну давайте,
пусть c — это минимальное натуральное число,
которое лежит в M.
Давайте поймем, какими свойствами должно обладать c.
Значит, во-первых, у нас c ≠ 1.
Ну действительно, потому что у нас a не делится на p по условию,
значит, a ∙ 1 не делится на p,
и значит, единица не принадлежит M.
Во-вторых, заметим,
что c у нас должно быть меньше, чем p.
Меньше либо равно, чем p.
Почему?
Потому что p принадлежит M.
То есть, смотрите, ap по определению делится на p.
Значит, у нас p принадлежит M.
Ну теперь давайте предположим, что c у нас меньше, чем p.
Значит, если такое случится, то так как у нас c лежит в M и p лежит в M,
то и остаток от деления p на c тоже лежит в M.
[ПИШЕТ НА ДОСКЕ]
[ПИШЕТ НА ДОСКЕ] [ПИШЕТ
НА ДОСКЕ] Ну смотрите, что здесь происходит.
Значит, c у нас больше 1, меньше p.
А p — простое число.
Это значит, что p не может делиться на c нацело.
Это значит, что остаток от деления p на c, он не нулевой.
То есть, если я напишу здесь остаток r, то r ≠ 0.
И по нашему свойству №3, r принадлежит M,
и с другой стороны, r меньше c, потому что это остаток.
Ну значит, мы получили меньшее число, чем c, которое все еще лежит в M.
Значит, это противоречие с минимальностью.
Значит, чему это противоречит?
Это противоречит утверждению, что c меньше, чем p.
Значит, это предположение неверно и c = p.
Отсюда мы получаем, что c = p.
Но раз c = p, это означает,
что, давайте теперь из этого выведем, что b у нас делится на p.
Заметим, что...
5-е свойство: b с очевидностью лежит в M.
Потому что по нашему предположению ab делится на p.
И если b не делится на p,
то тогда у нас есть остаток [ПИШЕТ
НА ДОСКЕ] [ПИШЕТ
НА ДОСКЕ] от деления b на p,
которое будет меньше, чем p и тоже будет лежать в M.
Но это — противоречие, потому что мы только что поняли, что у нас нет чисел
меньших, чем p, которые лежат в M, потому что p — это минимальное натуральное число.
Но это — противоречие.
Ну следовательно, b делится на p.
Вот.
Таким образом мы доказали,
что если у нас ab делится на p и a не делится на p,
то b делится на p.
Все.