Математика 5-6 классы. 20. Разложение чисел на простые множители

Подробности: Категория: Математика 5-6 классы

Разложение на простые множители

Доказательство бесконечности числа простых чисел

Доказательство основной теоремы арифметики

Разложение на простые множители

При рассмотрении все больших и больших натуральных чисел простые числа встречаются все реже. Для иллюстрации смысла этого утверждения отметим, что всего имеется,

168 простых чисел между 1 и 1000,

135 простых чисел между 1000 и 2000,

127 простых чисел между 2000 и 3000,

120 простых чисел между 3000 и 4000,

119 простых чисел между 4000 и 5000.

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

Каждое натуральное число, кроме числа 1, либо простое, либо может быть разложено на простые множители. Рассмотрим, например, натуральное число 94 860. Оно, очевидно, не простое, поскольку

94860=10 X 9486.

Кроме того, 9486 делится на 2, а также на 3 и, более того, на 9. Следовательно, можно написать

94860= 10 X 2 X 9 X 527 = 2 X 2 X 3 X 3 X 5 X 527.

Если бы число 527 было простым, то это выражение было бы разложением 94 860 на простые множители. Но 527 не является простым, поскольку 527=17x31. Разложение числа 94 860 на простые множители имеет, таким образом, вид

94860 = 2 X 2 X 3 X 3 X 5 X 17 X 31.

Мы рассмотрели определенное число 94 860; но тот же самый процесс применим к любому натуральному числу п. Действительно, либо n простое число, либо — не простое. Если оно не простое, то его можно разложить в произведение двух меньших чисел, скажем, а и b, n = ab. Каждое из чисел а, b в свою очередь либо простое, либо может быть разложено в произведение еще меньших чисел. Продолжая этот процесс, мы в конце концов получим разложение n на простые множители.

В первой фразе предыдущего абзаца простые числа выделяются из множества всех других натуральных чисел. В математике часто желательно делать определения настолько общими, чтобы становилось ненужным выделение отдельных случаев. Под «разложением на простые множители», например, понимается разложение числа, скажем 12, в произведение нескольких простых чисел, в нашем случае 2 x 2 x 3. Обобщим теперь понятие «разложение на простые множители» таким образом, чтобы оно включало случай единственного множителя. При этом, например, простое число 23 будет иметь разложение на простые множители, состоящее из единственного множителя 23. Используя это обобщенное понимание «разложения на простые множители», наше первоначальное утверждение можно заменить на следующее: «Каждое натуральное число, отличное от числа 1, может быть разложено на простые множители». Таким образом, мы укоротили определение и исключили необходимость различения того, является ли рассматриваемое натуральное число простым или нет; по крайней мере это различие становится ненужным в формулировке утверждения о разложении натуральных чисел на простые множители.

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

94 860 = 3 x 17 x 2 x 5 x 31 x 3 x 2.

Однако, за исключением подобных изменений порядка, для 94 860 нельзя указать никакого другого разложения. Этот результат известен как теорема о единственности разложения на множители или основная теорема арифметики.

Основная теорема арифметики. Каждое натуральное число, отличное от 1, может быть разложено в произведение простых множителей, и притом лишь единственным способом, если отвлечься от порядка следования множителей.

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

Приведенная выше формулировка основной теоремы арифметики объясняет одну из причин, почему число 1 не включено в совокупность простых чисел. Именно если число 1 считать простым, то можно было бы написать, например,

35 = 5 x 7 = 1 x 5 x 7,

т. е. число 35 (равно как и любое другое натуральное число) разлагалась бы в произведение простых множителей более чем одним способом. Конечно, основная теорема арифметики по-прежнему была бы верна, однако ее формулировка потребовала бы больше оговорок типа «за исключением...» или «если не...». Таким образом, исключение числа 1 из совокупности простых чисел позволяет формулировать результаты короче и изящнее.

Доказательство бесконечности числа простых чисел

Используемое здесь рассуждение представляет собой так называемое косвенное доказательство, именуемое также доказательством от противного, или r'eductio ad absurdum (приведением к абсурду). В доказательстве такого типа допускается, что сделанное предположение ложно, а затем из этого допущения выводится противоречие. В случае рассматриваемого предложения мы предполагаем, таким образом, что имеется лишь конечное число простых чисел.

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

Это обозначение подразумевает, что всего имеется k простых чисел, где k —некоторое натуральное число. Если считать, что простые числа перечислены в порядке возрастания, то, конечно,p₁= 2, p₂ = 3, p₃=5, р₄=7 и т. д. Тем не менее в процессе доказательства удобнее использовать обозначения р₁, р₂, р_з и т. д. вместо 2, 3, 5 и т. д.

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

ное число n, получающееся от перемножения всех простых чисел и последующего добавления единицы:

Число n не делится на p₁, поскольку при делении n на p₁ частное и остаток равны соответственно Р₂, Р_з .... Р_k и 1. Если бы n делилось на р₁, то остаток был бы равен 0. Значит, n не делится на р₁.

Аналогично доказывается, что n не делится ни на одно из чисел р₂, р₃, p₄ ..Р_k

Мы построили число n, не делящееся ни на одно простое число; но такого числа, конечно, быть не может. Таким образом, допущение, что имеется лишь конечное число простых чисел, привело к логическому противоречию. Следовательно, это допущение ложно. Тем самым доказано, что число простых чисел бесконечно.

Доказательство основной теоремы арифметики

В настоящем приложении доказывается, что каждое натуральное число, отличное от 1, может быть разложено в произведение простых множителей лишь единственным способом, если отвлечься от порядка следования множителей. При этом понимается, что натуральное число, являющееся простым, как, например, 23, само .является своим «разложением на простые множители». Рассматриваемое утверждение легко проверить для маленьких натуральных чисел. Например, 10 можно разложить в произведение 2 • 5, и по опыту мы знаем, что других разложений у 10 нет. То же самое верно и для всех чисел, меньших 10:

2 = 2, 3 = 3, 4 = 2 • 2, 5 = 5, 6 = 2 • 3,

7 = 7, 8 = 2 • 2 • 2, 9 = 3 • 3, 10 = 2 • 5.

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

Мы должны обратиться, таким образом, к математическому рассуждению. Натуральные числа от 2 до 10 были выше перечислены, и мы видели, что каждое из них разлагается на простые множители единственным образом. Далее, либо этот список можно продолжить неограниченно, и тогда все натуральные числа разлагаются на простые множители единственным образом, либо на некотором этапе продолжения свойство единственности разложения нарушается. Имеются лишь эти две возможности. Нашей целью является доказательство того, что в действительности имеет место первая возможность. Мы воспользуемся для этого косвенным рассуждением: допустим, что имеет место вторая возможность, т. е. что на некотором этапе перечисления натуральных чисел свойство единственности разложения на простые множители нарушается, и покажем, что такое допущение приводит к противоречию.

Прежде чем проводить это довольно длинное рассуждение во всех деталях, дадим для ориентировки читателя его краткий набросок.

Обозначим через m первое из чисел, которое можно разложить на простые множители более чем одним способом, и рассмотрим два различных разложения m на простые множители. В части I доказательства будет показано, что никакой из простых множителей одного разложения m не встречается в другом разложении. Показав, что если m имеет два разных разложения, то все простые множители одного разложения отличны от всех простых множителей другого разложения, мы затем построим в части II доказательства число n, меньшее чем ту также имеющее два разных разложения на простые множители. Тем самым мы получим противоречие с допущением, что m есть наименьшее целое число, обладающее двумя различными разложениями на простые множители, и это завершит доказательство.

Итак, пусть m — первое натуральное число, которое можно разложить на простые множители более, чем одним споcобом. Иными словами, мы предполагаем, что каждое, меньшее чем m, натуральное число разлагается единственным образом, а разложение m не единственно. Согласно предположению, имеется по крайней мере два различных разложения числа m. Пусть это будут разложения

При этом обозначении подразумевается, что для m имеется разложение на простые множители p₁, р₂, p_з и т. д. вплоть до р_r ,а также имеется другое разложение на простые множители q₁, q₂, q_з_и т. д. вплоть до q_s. Во втором разложении последний член обозначен через q_s, а не через q_r, потому что мы не можем, исходя из известных нам фактов, предполагать равенство числа простых множителей в обоих разложениях.

Введенное обозначение требует еще дальнейших пояснений. Вовсе не имеется в виду, что, как это было выше, p₁ есть лишь иное обозначение для простого числа 2, p₂ — иное обозначение для простого числа 3 и т. д. Нам вообще неизвестно принадлежит или нет простое число 2 совокупности p₁, p₂, ..., Р_r.Таким образом, p₁ может быть равным простому числу 2, или простому числу 23, или простому числу 47, или ни одному из них. Это есть попросту некоторое простое число. Точно так же p₂ есть некоторое простое число. Оно может как совпадать, так и не совпадать с р₁. Единственное, что мы предполагаем это возможность разложить натуральное число m на простые множители двумя различными способами.

Доказательство. Часть I. Покажем, что все простые числа p₁, p₂, ...., Р_r из первой совокупности отличны от всех простых чисел q₁, q₂, ...., q_s из второй совокупности. Таким образом, если, например, простое число 7 принадлежит первой совокупности, то оно не может принадлежать второй совокупности. Поскольку это вовсе не очевидно, мы должны дать соответствующее доказательство. Предположим, что имеется простое число, принадлежащее обеим совокупностям. Изменив если нужно, обозначения, мы можем считать, что совпадают первые числа обеих совокупностей, т. е. что p₁ = q₁ (Это можно сделать, поскольку в каждом разложении простые числа могут находиться в любом порядке.) Заменяя во втором разложении q₁ на р₁ мы получаем, что имеются следующие два разложения:

Деля эти равенства на р₁, находим

Мы пришли к двум различным разложениям натурального числа m/p₁, поскольку мы исходили из двух различных разложений для m. Но это невозможно, так как m, согласно предположению, есть наименьшее число, обладающее более, чем одним разложением, a m/p₁ меньше m.

Часть II. Итак, нами установлено, что все простые числа р₁, p₂, ..., р_r из первого разложения m отличны от всех простых чисел q₁, q₂, ..., q_s из второго разложения т. В частности, p₁ не равно q₁, что можно записать как p₁≠q₁. Предположим, что р₁ есть наименьшее из чисел р₁, q₁ т. е. что p₁<q₁. Мы вправе это сделать в силу полной симметрии обозначений в обеих совокупностях простых чисел. Таким образом, если мы проведем доказательство в случае p₁<q₁, то по симметрии аналогичное доказательство применимо к случаю p₁>q₁ с р, замененными на q, и наоборот.

Предполагая, что p₁<q₁ мы укажем число, которое меньше, чем m, но имеет два различных разложения. Тем самым доказательство будет завершено, поскольку существование такого числа противоречит сделанному нами допущению, что m есть наименьшее натуральное число, обладающее более, чем одним разложением. Таким числом является

Обратим внимание на то, как строится число n: оно равно произведению q₁—р₁ и простых чисел q₂, q₃,... ...q_s- Его можно записать в виде разности:

или

Из этой записи видно, что n меньше m, поскольку число р₁q₂q₃....q_s положительно.

Установим, наконец, что натуральное число n имеет два различных разложения. Для этого рассмотрим n в той его форме, в которой оно было введено а именно:

Все числа q₂, q₃,...., q_s являются простыми, но число q₁—p₁ не обязательно простое. Если q₁—р₁ разложить на простые множители, то мы получим такое разложение n, которое не содержит простого числа р₁ в качестве множителя. Для доказательства этого заметим сначала, что, как показано в части I доказательства, число p₁ не встречается среди чисел q₂, q₃, ..., q_s. Далее, как бы число q₁—p₁ ни разлагалось на простые множители, простое число p₁ не может оказаться среди них. В самом деле, если бы р₁ было множителем в разложении q₁—p₁ на простые множители, то р₁ было бы делителем q₁—p₁. Иными словами, выполнялось бы равенство

где b есть частное от деления q₁-— р₁ на p₁. Но из этого равенства следуют равенства

последнее из которых можно понимать как утверждение, что p₁ есть делитель q₁. Такое утверждение, конечно, ложно, поскольку никакое простое число не является делителем другого простого числа.

Покажем далее, что n имеет также другое разложение на простые множители, в которое входит р₁. Для этого вернемся к выведенному ранее равенству

Заменяя в нем m по формуле

получаем

Стоящее в скобках число не обязательно является простым; однако если его разложить на простые множители, то мы получим разложение на простые множители для n, включающее р₁. Таким образом, нами указано два разложения n (или, скорее, два способа получения разложений n на простые множители), одно из которых содержит простое число р₁ в качестве множителя, а другое не содержит. Иными словами, число n, будучи меньше m, имеет два различных разложения на простые множители. Тем самым теорема доказана ).