Ведя неспешный разговор о натуральных числах, мы основное внимание обращали на то, как именно у них проводятся всевозможные операции. А вот о свойствах самих чисел сказали достаточно мало. Дело в том, что математические множества далеки от идеалов анархической демократии, здесь элементы могут быть совершенно не равны между собой, а то и вовсе обладать исключительными, невиданными качествами. Именно ими может похвастаться подмножество простых чисел \mathbb P (prime numbers), входящее в \mathbb N.

Rendered by QuickLaTeX.com

Что такое простые числа? Согласно определению, это такие числа, у которых только два делителя — единица и они сами. То есть, 3 это простое число, так как ни на что, кроме 3 и 1 вы его поделить не можете. Таким же простым является 5, 7, 11 и многие многие другие. Первое по очереди следования простое число, с которым мы сталкиваемся, это двойка. Почему не единица? А просто из-за соображений удобства. Долгое время единица тоже считалась простым числом, но необходимость дополнительно исключать её из доказательств различных теорем сыграла свою роль, после чего её статус был безжалостно понижен.

Может, мы некоторые числа и можем делить лишь определённым образом, что с того, почему для них надо изобретать отдельные категории? Некоторой запутанности в этом вопросе способствует и само название, «простые числа» кажутся заведомо чем-то несерьёзным, пустяковым. Между тем, простые числа «просты» ровно настолько, насколько «элементарна» элементарная физика или очевиден низкоуровневый язык программирования. «Простота» тут означает первичность, изначальную данность, помпезную фундаментальность. Если угодно, можно представлять простые числа как детали конструктора, из которых не в меру активные детишки составляют всё новые и новые (зачастую весьма уродливые) фигуры.

Определяя всё множество \mathbb N, мы сказали, что оно порождается единицей, и это совершенно правильно. Но дело в том, что представлять любое число как сумму единиц не особо продуктивно — никакой новой информации нам это не скажет, ни к каким практическим выводам не подтолкнёт. Куда как полезнее уметь раскладывать числа на множители, особенно если этих чисел у вас много и со всеми ними требуется что-то сделать.

Иначе это называется «факторизацией», в которой именно простым числам отводится ведущая роль. Почему? А потому, что, согласно основной теореме арифметики, любое число можно представить как произведение какого-то количества простых чисел. Иначе говоря, любое число, которое мы можем взять, окажется либо простым, либо произведением конечного набора простых чисел. Именно в этом смысле простые числа являются первозданным частицами, порождающими всю остальную количественную вселенную.

Так-так-так… Что тут у нас, какие-то «основные теоремы»? А с чего мы их мимоходом принимаем за истину? Немедленно исправимся. «Теоремами» в математике называются какие-то доказанные утверждения, при этом в самом процессе доказательства мы уже исходим из некоторых предпосылок (они зовутся «аксиомами», которые принимаются нами за правдивые). Скажем, вы собираетесь на вечеринку, приняв за безусловную истину, что на ней вы потребите не менее 3-х литров крепкого алкоголя, отведя на сон порядка 2-х часов под раннее утро. Из этого всего можно сделать вывод, что на следующий день самочувствие будет весьма скверное, назвав сказанное «теоремой пятничного вечера».

maga

 

 

Так просто вперёд идти нельзя, сила за тобой должна быть, твёрдо опираться на что-то надо. Хочешь по-уму рассудить, как там дела обстоят? Подумай, с чего начинать будешь, чем мысль свою обосновывать. Но только туда-сюда не метайся, раз начал. Если чего изначально за правду принял, этой позиции и дальше держись. А то уважать тебя не будут, за несерьёзного человека сочтут.

 

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

В каком-то смысле именно ограниченный инструментарий позволил им сделать акцент на одной из важнейших особенностей математического мышления — открывать новое надо, опираясь на уже изученное. Мощнейший потенциал этого подхода мы увидим позже, когда обратимся к геометрии, а пока давайте слегка побарахтаемся на мелководье. На роль мелководья у нас будет выбран алгоритм Эвклида по поиску наибольшего общего делителя. Почему именно он? Во-первых, потому что до сих пор является крайне удобным способом этот общий делитель для чисел находить. Во-вторых, потому что серьёзно поможет в дальнейших рассуждениях, не только в рамках данной статьи.

Допустим, у нас имеется несколько отрезков (т.е. чисел) разной длины, как узнать, какой общий их делитель окажется наибольшим? Точнее, как это всё узнать, не перебирая всех возможных кандидатов на эту роль? Удивительно полезно обратиться к методу исчерпания, когда при помощи одного мы определяем, «исчерпываем» другое. И это не просто что-то там за неведомая придумка, метод исчерпания лежал в основе всей греческой математики, да и в нашем изложении играет не последнюю роль. Возьмём, к примеру, числа 124 и 93, схематично изобразим их уже полюбившимися кубиками.

Rendered by QuickLaTeX.com

Так сходу не очень получится сказать, можно ли одновременно оба эти числа разделить на что-то, кроме единицы. Как хорошо, что греки это всё продумали до нас и даже сочинили детальный алгоритм! Для его реализации нужно попробовать выразить наибольший отрезок через наименьший и посмотреть, что останется, иначе говоря, выполнить деление с остатком. В нашем случае совершенно ясно, что больше, чем один раз, чёрный отрезок внутри красного не поместится. Ну так и не страшно, сохраним себе этот отрезочек на память, да заодно его цвет поменяем.

Rendered by QuickLaTeX.com

Готово, теперь в нашем распоряжении совершенно очаровательный отрезок размером в 124-93=31 фиолетовую ячейку. Но как это нам поможет? Для ответа на этот вопрос проделаем только что осуществлённую операцию, только теперь будем исчерпывать чёрный отрезок при помощи вновь полученного, фиолетового.

Rendered by QuickLaTeX.com

Вот так номер получился — наш новый отрезок уместился в чёрном ровно три раза, не оставив никакого остатка. Это значит, дамы и господа, что мы нашли наибольший общий делитель (или НОД, просьба не путать аббревиатуру со знаменитым «общественным движением» для психически больных) для первоначальных чисел, равный 31. Впрочем, мы могли оказаться вовсе не такими везучими, если бы подобный процесс пришлось прокручивать 7, 10, 69 и больше раз, снова и снова укорачивая все получаемые отрезки. В итоге был риск прийти к выводу, что единственным общим делителем может служить лишь единица — в таком случае два числа назывались бы взаимно простыми (например, таковыми являются 3 и 7).

Рассмотренный алгоритм хорош (помимо прочего) тем, что помогает явно увидеть, как одни числа составляют другие, а те, в свою очередь, третьи и так далее. Далее, можно сделать некоторые заключения и о методике получения всех чисел в принципе. Любые взятые могут быть либо простыми, либо произведением каких-то простых чисел. Почему? А вот допустим, у нас есть некое число, называемое Q. Оно либо простое, и тогда ни на какие множители не раскладывается, либо обычное, т.е. составное, являющееся произведением каких-то a \cdot b \cdot c и так далее. Но каждое a, b, c и так далее сами могут быть либо простыми, либо точно так же раскладываться на множители. Проводя этот процесс снова и снова, мы в итоге придём к какому-то набору гарантированно простых чисел, чьё произведение и даст нам число Q.

nerd

 

Всякое разложение на простые множители, поиск делителей, изучение удивительных особенностей отдельных чисел важно не только потому, что невероятно интересно. На этих операциях и свойствах основывается большое количество чисто практических задач, например, в области шифрования. Собственно, один из самых популярных криптографических алгоритмов RSA опирается как раз на ту идею, что разложение очень большого числа на простые множители занимает кучу времени, при условии, что у вас нет необходимых для этого данных. И да, в RSA тоже используется алгоритм Эвклида. Вы себе такое представляете? Как захватывающе! Да? ДА???

 

 

Сама основная теорема арифметики стоит как раз в этом, однако помимо того, что в ней говорится о возможности разложить любое число в произведение простых, отдельно замечается, что такое разложение единственно. Доказать это ещё проще, чем в современной России угодить в тюрьму за репост политически окрашенной публикации. А именно, предположим, что мы нашли несколько совершенно разных вариантов разложения числа Q, первый — это произведение p_1 \cdot p_2 \cdot p_3 \ldots p_n, ну а второй — это q_1 \cdot q_2 \cdot q_3 \ldots q_n, при этом количество множителей в обоих разложениях не обязательно должно совпадать.

Начнём рассматривать, что тут у нас получается. Для начала возьмём число p_1 и хорошенько просверлим взглядом. Так как Q получено в том числе умножением p_1 на что-то, само Q вполне ожидаемо на это самое p_1 спокойно делится. Но раз так, то на p_1 делится и q_1 \cdot q_2 \cdot q_3 \ldots q_n (так как это просто другой способ записи числа Q), а это возможно только если одно из q_i равно p_1. В очередной раз повторяя всё это в отношении всех остальных множителей до счастливого конца, мы устанавливаем, что оба разложения не могут сделать ничего другого, кроме как полностью совпасть между собой, а значит, основная теорема арифметики оказывается доказана. Рассуждение вроде бы пустяковое, только по масштабу своих последствий сравнится разве что с изобретением колеса.

Забьём последний гвоздь в узорчатый саркофаг знаний, которые едва ли когда-то вновь потревожим. Покажем, что простых чисел бесконечно много. Совсем как в предыдущие разы, будем рассуждать «от противного», то есть допустим, что это не так и посмотрим, к каким выводам нас это приведёт. Итак, пусть простые числа конечны и у нас есть их полный список p_1, p_2, p_3 \ldots p_n. Мы можем умножить их друг на друга, получив в итоге какое-то Q, которое, само собой, делится на каждое из наших p_i. А теперь возьмём и прибавим к Q всего лишь одну единицу. Свежие новости про Q+1? Ну, оно должно раскладываться на какие-то простые множители (согласно основной теореме), при этом само по себе простым числом быть не может, ведь у нас и так был полный их список.

Выходит, что среди этих множителей будет как минимум одно из наших p_i. Но тогда это самое p_i должно без проблем делить Q+1 на равные части, а в нашем случае остаётся остаток, равный единице, какое бы из известных простых чисел мы не взяли. Значит, Q+1 либо само является простым числом, либо существуют ещё какие-то простые числа, делящие Q+1, но не включённые в наш список. Что из этого следует, вы догадываетесь и сами — множество простых чисел содержит бесконечно много элементов.

 

Ой, ну не знаю… Все эти множители, формулы какие-то, произведения… Мне так не очень понятно. А вот алгоритм Эвклида нравится, я его на цветных ленточках хорошо понимаю! Про количество простых чисел я бы так и сделала — берёте вот ленточку длиной в Q+1 и ещё кучу других, покороче, которые у нас за все простые числа идут. Ну вот, и по очереди каждой «простой» ленточкой  это Q+1 пытаетесь поделить. В итоге у вас во все разы единичка лишняя и останется, гарантирую!

 

 

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

Хотя вот вам небольшой спойлер — нежелающие утруждать себя всякой там факторизацией через пару десятков статей обнаружат, что к этому их всё равно принудит беспристрастная действительность. Да и не просто принудит, ещё и бонусов всевозможных за это умение накидает.