Ведя неспешный разговор о натуральных числах, мы основное внимание обращали на то, как именно с ними проводятся всевозможные операции. А вот о свойствах самих чисел сказали мало. Дело в том, что математические множества далеки от идеалов анархической демократии, здесь элементы могут быть совершенно не равны между собой, а то и вовсе обладать исключительными, невиданными качествами. Именно ими может похвастаться подмножество простых чисел (prime numbers), входящее в .
Простые числа?
Что такое простые числа? Согласно определению, это такие числа, у которых только два делителя — единица и они сами. То есть, это простое число, так как ни на что, кроме и вы его поделить не можете. Таким же простым являются и многие многие другие. Первое по очереди простое число, с которым мы сталкиваемся, это двойка. Почему не единица? А просто из-за соображений удобства. Долгое время единица тоже считалась простым числом, но необходимость дополнительно исключать её из доказательств различных теорем сыграла свою роль, после чего статус был безжалостно понижен.
Простое число. Натуральное число называется простым, если оно делится без остатка только на и на само .
Может, мы некоторые числа и можем делить лишь определённым образом, что с того, почему для них надо изобретать отдельные категории? Некоторой запутанности в этом вопросе способствует и само название, “простые числа” кажутся заведомо чем-то несерьёзным, пустяковым. Между тем, простые числа “просты” ровно настолько, насколько “элементарна” элементарная физика. “Простота” тут означает первичность, изначальную данность, фундаментальность. Если угодно, можно представлять простые числа как детали конструктора, из которых не в меру активные детишки составляют всё новые и новые (иногда весьма уродливые) фигуры.
Разложение на множители и алгоритм Эвклида
Определяя всё множество , мы сказали, что оно порождается единицей, и это совершенно правильно. Но дело в том, что представлять любое число как сумму единиц не особо продуктивно — никакой новой информации нам это не даст, ни к каким практическим выводам не подтолкнёт. Куда как полезнее уметь раскладывать числа на множители, особенно если этих чисел у вас много и со всеми ними требуется что-то сделать.
Иначе это называется факторизацией, в которой именно простым числам отводится ведущая роль. Почему? А потому, что, согласно Основной теореме арифметики, любое число можно представить как произведение какого-то количества простых чисел. Иначе говоря, любое число, которое мы можем взять, окажется либо простым, либо произведением конечного набора простых чисел. Именно с этой точки зрения простые числа являются первозданным частицами, порождающими всю остальную количественную вселенную.
Факторизация. Факторизацией или факторингом называется разложение объектов на произведение других, менее сложных объектов. Например, разложение числа на составляющие его множители.
Так-так-так… Что тут у нас, какие-то “основные теоремы”? А с чего мы их мимоходом принимаем за истину? Немедленно исправимся. “Теоремами” в математике называются доказанные утверждения, при этом в самом процессе доказательства мы уже исходим из некоторых предпосылок (они зовутся аксиомами, которые изначально принимаются нами за правдивые). Скажем, вы собираетесь на вечеринку, приняв за безусловную истину, что на ней вы потребите не менее 3-х литров крепкого алкоголя, отведя на сон порядка 2-х часов под раннее утро. Из этого всего можно сделать вывод, что на следующий день самочувствие будет весьма скверное, назвав сказанное “теоремой пятничного вечера”.
Так просто вперёд идти нельзя, сила за тобой должна быть, твёрдо опираться на что-то надо. Хочешь по-уму рассудить, как там дела обстоят? Подумай, с чего начинать будешь, чем мысль свою обосновывать. Но только туда-сюда не метайся, раз начал. Если чего изначально за правду принял, этой позиции и дальше держись. А то уважать тебя не будут, за несерьёзного человека сочтут.
Покажем это на примере, однако попробуем штурмовать Основную теорему не в лобовой атаке, а сперва осуществим необходимые приготовления. Начнём, обратившись к наследию древних греков: как никак, они были одними из первых, кто об этих простых числах и теоремах основательно задумался. Никогда не стоит недооценивать, к каким результатам могут прийти незаурядные умы при наличии большого количества свободного времени и кучи рабов, удовлетворяющих различные бытовые потребности. То есть, греки, например, не знали современной формальной записи, выражая все соображения при помощи линий, треугольников, кружков и тому подобного, но любознательности им было точно не занимать.
В каком-то смысле именно ограниченный инструментарий позволил им сделать акцент на одной из важнейших особенностей математического мышления — открывать новое надо, опираясь на уже изученное. Мощнейший потенциал этого подхода мы увидим позже, когда обратимся к геометрии, а пока давайте слегка побарахтаемся на мелководье. На роль мелководья у нас будет выбран алгоритм Эвклида по поиску наибольшего общего делителя. Почему именно он? Во-первых, потому что до сих пор является крайне удобным способом этот общий делитель для чисел находить. Во-вторых, потому что серьёзно поможет в дальнейших рассуждениях, не только в рамках данной статьи.
Допустим, у нас имеется несколько отрезков (т.е. чисел) разной длины, как узнать, какой общий их делитель окажется наибольшим? Точнее, как это всё узнать, не перебирая всех возможных кандидатов на эту роль? Удивительно полезно обратиться к методу исчерпания, когда при помощи одного мы определяем, “исчерпываем” другое. Возьмём, к примеру, числа и и отождествим их с отрезками аналогичной длины (если не верите, что размеры верны, можете увеличить масштаб и сосчитать пиксели):
Так сходу не очень получится сказать, можно ли одновременно оба эти числа-отрезка разделить на что-то, кроме единицы. Как хорошо, что греки это всё продумали до нас и даже сочинили детальный алгоритм! Для его реализации нужно попробовать выразить наибольший отрезок через наименьший и посмотреть, что останется, иначе говоря, выполнить деление с остатком. В нашем случае совершенно ясно, что больше, чем один раз, меньший (синий) отрезок внутри большего не поместится. Ну так и не страшно, сохраним себе этот остаток на память, заодно укажем его точный размер:
Готово! Теперь в нашем распоряжении совершенно очаровательный отрезок длиной в . Но как это нам поможет? Для ответа на вопрос проделаем только что осуществлённую операцию, но теперь будем исчерпывать меньший, синий отрезок при помощи вновь полученного (“остаточный” отрезок посередине выделим белым, чтобы не сливалось):
Вот так номер получился! Наш остаток уместился в синем отрезке ровно три раза, не оставив никакого нового остатка, т.е. на его основе мы можем исчерпать весь синий отрезок без лишних частей.
Это значит, дамы и господа, что мы нашли наибольший общий делитель (или НОД, просьба не путать аббревиатуру со знаменитым “общественным движением”) для первоначальных чисел, равный . Впрочем, мы могли оказаться вовсе не такими везучими, если бы подобный процесс пришлось прокручивать и больше раз, снова и снова укорачивая все получаемые отрезки. В итоге был риск прийти к выводу, что единственным общим делителем может служить лишь единица — в таком случае два числа назывались бы взаимно простыми (например, таковыми являются и ).
Алгоритм Эвклида. Допустим, у нас есть два натуральных числа и . Если , то . Иными словами, в умещается какое-то количество плюс некий (возможно нулевой) остаток, который всегда меньше . Скажем, для пары чисел имеем . Сам алгоритм состоит в том, что найдя остаток для изначальных , мы повторяем процедуру, но уже для чисел , получая новый остаток . Будем делать это снова и снова, пока не придём к нулевому остатку, т.е. узнаем, что наконец-то можно ровно поделить.
Основная теорема арифметики
Рассмотренный алгоритм хорош (помимо прочего) тем, что помогает явно увидеть, как одни числа составляют другие, а те, в свою очередь, третьи и так далее. Далее, можно сделать некоторые заключения и о методике получения всех чисел в принципе. Любое случайно взятое число может быть либо простым, либо произведением каких-то простых чисел. Почему? А вот допустим у нас есть некое число, называемое . Оно либо простое, и тогда ни на какие множители (кроме самого себя и единицы) не раскладывается по определению, либо обычное, т.е. составное, являющееся произведением каких-то и так далее. Но каждое и так далее сами могут быть либо простыми, либо точно так же раскладываться на множители. Проводя этот процесс снова и снова, мы в итоге придём к какому-то набору гарантированно простых чисел, чьё произведение и даст нам число .
Всякое разложение на простые множители, поиск делителей, изучение удивительных особенностей отдельных чисел важно не только потому, что невероятно интересно. На этих операциях и свойствах основывается большое количество чисто практических задач, например, в области шифрования. Собственно, один из самых популярных криптографических алгоритмов RSA опирается как раз на ту идею, что разложение очень большого числа на простые множители занимает кучу времени, при условии, что у вас нет необходимых входных данных. И да, в RSA тоже используется алгоритм Эвклида. Вы себе такое представляете? Как захватывающе! Да? ДА???
Сама основная теорема арифметики стоит как раз в этом, однако в ней дополнительно замечается, что разложение любого числа на произведение простых единственно.
Основная теорема арифметики. Любое натуральное число можно представить как произведение в котором все — простые числа. Кроме того, такое представление единственно.
Доказать это ещё проще, чем в современной России угодить в тюрьму за репост политически окрашенной публикации. А именно, предположим, что мы нашли несколько совершенно разных вариантов разложения числа , первый — это произведение , ну а второй — это , при этом количество множителей в обоих разложениях не обязательно должно совпадать.
Начнём рассматривать, что тут у нас получается. Для начала возьмём число и хорошенько просверлим взглядом. Так как получено в том числе умножением на что-то, само вполне ожидаемо на это самое спокойно делится. Но раз так, то на делится и (так как это просто другой способ записи числа ), а это возможно только если одно из равно . В очередной раз повторяя всё это в отношении всех остальных множителей до счастливого конца, мы устанавливаем, что оба разложения не могут сделать ничего другого, кроме как полностью совпасть между собой, а значит, основная теорема арифметики оказывается доказана. Рассуждение вроде бы пустяковое, только по масштабу своих последствий сравнится разве что с изобретением колеса.
Хм… Гладко стелишь, но что-то тут не так, нутром чувствую! Нужно же одно через другое вывести, а тут всё в кучу намешано! Ну, в смысле… Ладно, не идёт мысль, попозже соберусь и всё как надо раскидаю. Я уж думал, хоть тут за спиной дела мутить не будут.
Бесконечность простых чисел
Забьём последний гвоздь в узорчатый саркофаг знаний, которые едва ли когда-то вновь потревожим. Покажем, что простых чисел бесконечно много. Совсем как в предыдущие разы, будем рассуждать “от противного”, то есть допустим, что это не так и посмотрим, к каким выводам нас это приведёт.
Итак, пусть простые числа конечны и у нас есть их полный список: . Мы можем умножить их друг на друга, получив в итоге какое-то , которое, само собой, делится на каждое из наших . А теперь возьмём и прибавим к всего лишь одну единицу. Свежие новости про ? Ну, оно должно раскладываться на какие-то простые множители (согласно Основной теореме арифметики), при этом само по себе простым числом быть не может, ведь у нас и так был полный их список.
Выходит, что среди этих множителей будет как минимум одно из наших . Но тогда это самое должно без проблем делить на равные части, а в нашем случае всегда будет по итогам остаток, равный единице (т.к. без остатка на мы можем разделить только само ), какое бы из известных простых чисел мы ни взяли. Значит, либо само является простым числом, либо существуют ещё какие-то простые числа, делящие , но не включённые в наш список — противоречие с исходным условием. Что из этого следует, вы догадываетесь и сами: множество простых чисел содержит бесконечно много элементов.
Ой, ну не знаю… Все эти множители, формулы какие-то, произведения… Мне так не очень понятно. А вот алгоритм Эвклида нравится, я его на цветных ленточках хорошо понимаю! Про количество простых чисел я бы так и сделала — берёте вот ленточку длиной в и ещё кучу других, покороче, которые у нас за все простые числа идут. Ну вот, и по очереди каждой “простой” ленточкой это пытаетесь поделить. В итоге у вас во все разы единичка лишняя и останется, гарантирую!
В приложении с заданиями мы ещё раз посмотрим, как безошибочно искать общие делители, заранее понимать, на что делятся любые данные нам числа, а также побалуемся доказательством самых простых утверждений из элементарной теории чисел. То есть, всяких теорем о том, сколько чисел какого вида существует (или не существует), какие из них действительно простые, а какие — не очень. Учитывая, что никакого частого использования в учебной программе обычных школ или вузов (непрофильных дисциплин) эти вещи не имеют, отвлекаться на них могут себе позволить лишь самые увлечённые. Все остальные приглашаются сразу к следующей, более “практичной” публикации.
Хотя вот вам небольшой спойлер — нежелающие утруждать себя всякой факторизацией через пару десятков статей обнаружат, что к этому их всё равно принудит беспристрастная действительность. Да и не просто принудит, ещё и бонусов всевозможных за это умение накидает.