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

§ 90. Простые и составные числа. Всякое число, конечно, делится на единицу и само на себя. Существует очень много чисел, которые делятся не только на единицу и само на себя, но имеют еще и другие делители; например, число 30, кроме единицы и 30, имеет еще делители: 2, 3, 5, 6, и 15.

Всякое число, кроме единицы, которое делится только на единицу и само на себя, называется простым (или абсолютно простым, или первоначальным).

Число, которое делится не только на единицу и само на себя, но еще и на другие числа, называется составным (или сложным).

Число 1 не причисляется ни к простым, ни к составным числам, оно занимает особое положение.

Есть 25 простых чисел, меньших 100, а именно:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.

В конце этой книги приложена таблица, в которой выписаны все простые числа, меньше 6000.

§ 91. Разложение составного числа на простые множители. Всякое составное число можно разложить на простые множители, т. е. представить его в виде произведения простых чисел. Например, разложить 12 на простые множители – значит, представить это число так: 12 = 2 · 2 · 3.

Пусть требуется разложить на простые множители какое-нибудь составное число, например 420. Для этого находим (по признакам делимости) наименьшее простое число, на которое делится 420; такое число есть 2. Разделим 420 на 2:

420 : 2 = 210;

значит

420 = 210 · 2.     (1)

Теперь подыскиваем наименьшее простое число, на которое делится составное число 210; такое число есть 2. Разделим 210 на 2:

210 : 2 = 105,

значит,

210 = 105 · 2.

Заменим в равенстве (1) число 210 равным ему произведением:

420 = 105 · 2 · 2.     (2)

Наименьшее простое число, на которое делится составное число 105, есть 3. Разделим 105 на 3:

105 : 3 = 35,

значит

105 = 35 · 3.

Заменим в равенстве (2) число 105 равным ему произведением:

420 = 35 · 3 · 2 · 2.     (3)

Наименьшее простое число, на которое делится составное число 35, есть 5; разделив 35 на 5, находим 7; значит, 35 = 7 · 5. Заменив в равенстве (3) число 35 равным ему произведением 7 · 5, получим:

420 = 7 · 5 · 3 · 2 · 2.

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

Так как произведение не изменяется от перемены мест сомножителей, то можно писать их в каком угодно порядке; обыкновенно их пишут от меньших к большим, т.е. так:

420 = 2 · 2 · 1 · 5 · 7.

Разложение на простые множители удобнее всего записывать так:

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

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

В рассмотренном примере мы каждый раз искали наименьший простой делитель полученного числа; чаще всего это – самый удобный способ разложения, потому что чем меньше число,

тем легче на него делить; кроме того, для большинства малых делителей существуют простые признаки делимости. Однако указанный путь не является обязательным, и часто разложение на простые множители может бьть проще проведено другим порядком. Так, в нашем же примере мы сразу видим, что 420 делится на 10 = 2 · 5. Поэтому, произведя разложение (в уме),

мы можем написать

420 = 10 · 42 = 2 · 5 · 2 · 3 · 7 = 2 · 2 · 3 · 5 · 7

Если требуется, например, разложить на множители число 13 000, то мы можем сразу заметить, что 13 000 = 13 · 1000, а так как 13 простое число, то остается разложить на простые множители число

1000 = 10 · 10 · 10 = 2 · 5 · 2 · 5 · 2 · 5,

и мы сразу получаем:

13 000 = 2 · 2 · 2 · 5 · 5 · 5 · 13.

Возьмем еще пример. Разложим на простые множители 8874:

Дойдя до частного 493, мы затрудняемся решить, на какое число оно делится. В таких случаях обращаемся к таблице простых чисел (в конце этой книги). Если в ней встретится число, поставившее нас в затруднение, то оно делится только само на себя. Число 493 не находится в таблице простых чисел; значит, это число составное, и потому мы пробуем делить его на простые числа: 7, 11, 13 и т. д., до тех пор, пока нс дойдем до деления без остатка. Оказывается, что 493 делится на 17, причем в частном получается 29. Теперь можем окончить разложение.

Из этого примера видно, что иногда очень трудно выполнить разложение составного числа, так как при разложении мы можем встретиться с большим числом, о котором затруднительно решить, простое ли оно или составное; а если оно составное, то не всегда легко найти его наименьший простой делитель.

§ 92. Возведение в степень. При разложении чисел на множители, а также и во многих других случаях приходится часто писать несколько одинаковых сомножителей подряд, например 2 · 2 · 2 · 2 или 5 · 5 · 5. Подобно тому как для сложения равных слагаемых мы ввели особое наименование (умножение) и особое обозначение (2 · 4 вместо 2 + 2 + 2 + 2), так и для умножения равных сомножителей полезно ввести особое наименование и особое обозначение.

Произведение одинаковых сомножителей называется степенью. Так, 2 · 2 · 2 · 2 есть 2 в четвертой степени. Записывается это так:

2 · 2 · 2 · 2 = 24

при этом число 2 называется основанием степени, а число 4 – показателем степени. Самое же действие называется возведением числа 2 в четвертую степень. Точно так же,

5 · 5 · 5 = 53

читается: 5 в третьей степени; здесь 5 – основание, а 3 – показатель степени.

Вторую степень сокращенно называют квадратом данного основания, а третью степень – кубом его. Так, 72 читается «7 в квадрате», а 53 – «5 в кубе». Первой степенью числа называют само это число: 31 = 3. С помощью введенного обозначения с разложение чисел на простые множители часто может быть записано короче; так, в примерах, рассмотренных в § 91, мы можем написать:

420 = 22 · 3 · 5 · 7,
13 000 = 23 · 53 · 13.

Иногда такое сокращение может быть очень заметным; например, 1536 = 2 · 2 · 2 · 2 · 2 · 2 ·2 · 2 · 2 · 3 = 29 · 3.

§ 93. Составное число разлагается только в один ряд простых множителей. Легко доказать, что способом, описанным в § 91 п. 6, всякое составное число можно разложить на простые множители. Но, применяя этот способ, мы можем не придерживаться непременно того порядка, какой был нами указан, т.е. мы можем начинать разложение не с наименьшего простого числа, на которое делится составное, а производить разложение в какой-нибудь другой последовательности (и даже можем, как это мы видели, разложить составное число сначала на составные множители, а затем эти множители разложить на простые). Поэтому возникает вопрос: не могут ли иногда получиться для одного и того же составного числа два (или более) различных ряда простых множителей, которые отличались бы друг от друга или самими множителями, или числом повторения одинаковых множителей? Например, число 14 000 имеет разложение 24 · 53 · 7; не может ли оно иметь еще другое разложение, в которое входил бы какой-нибудь иной простой множитель, кроме 2, 5 и 7, или в котором эти множители повторялись бы какое-нибудь другое число раз, чем в разложении 24 · 53 · 7? Доказано, что этого быть не может, т. е. что составное число, как бы мы его ни разлагали, дает только один ряд простых множителей (которые, конечно, могут быть переставляемы).

Доказательство возможности и единственности разложения чисел на простые множители. Чтобы строго доказать, что всякое число (кроме единицы) может быть разложено, и притом только одним способом, на простые множители, дока>кем сначала следующие две теоремы.

Теорема 1. Всякое число, кроме единицы имеет, по крайней мере один простой делитель.

Доказательство. Пусть a ≠ 1; если a – число простое, то оно само будет своим простым делителем, и теорема доказана; если же a – число составное, то оно имеет делителей, отличных от a и от единицы; пусть b есть наименьший из этих делителей; тогда b не может быть составным числом, так как, если бы оно делилось на число c, отличное от единицы и от него самого, то на это число c делилось бы и число a, и, значит, b не было бы наименьшим делителем числа a. Поэтому b – число простое, а так как оно есть делитель числа a, то теорема доказана.

Теорема 2. Произведение нескольких сомножителей a1a2a3...an может делиться на простое число p только тогда, когда по крайней мере один из сомножителей делится на p.

Доказательство. Рассматривая данное произведение как произведение только двух сомножителей: а1 и (a2a3...an), мы можем рассуждать так: если a1 не делится на простое число p, то это значит, что a1 не имеет с p общих делителей, кроме единицы; в таком случае по доказанной в § 88 теореме число (a2a3...an) должно делиться на p. Подобно этому убедимся, что если a2 не делится на p, то число (a3a4...an) должно делиться на p. Продолжая эти рассуждения далее, найдем, что если ни одно из чисел: a1, a2, a3, …, an-1 не делится на p, то an делится на p. Итак, какое-нибудь из чисел: a1, a2, a3, …, an делится на p.

Чтобы доказать теперь возможность разложения любого числа, кроме единицы, на простые множители, поступаем так. Пусть а ≠ 1; если a – число простое, то утверждение доказано; если же a – число составное, то по теореме 1 оно имеет простой делитель p1; пусть

a = p1a1;

если a1 – число простое, то теорема доказана; если же оно составное, то по теореме 1 оно имеет простой делитель p2; пусть

a1 = p2a2,

так что

a = p1p2a2;

если a2 – число простое, то теорема доказана; если оно составное, то мы продолжаем рассуждать указанным образом. Так как a > a1, a1 > a2 и т. д., то наше разложение должно рано или поздно закончиться; но закончиться оно может только тогда, когда какое-нибудь an окажется числом простым (если оно составное, то мы можем продолжать разложение); поэтому разложение

a = p1p2...pn-1an

есть разложение числа a на простые множители, возможность которого таким образом доказана.

Для доказательства единственности разложения будем рассуждать так:

пусть для некоторого числа мы имеем два разложения на (одинаковые или различные) простые множители:

abc… и a1b1c1... ,

тогда

abc = a1b1c1... .

Левая часть последнего равенства делится на a; значит, и правая часть должна делиться на a. Но a – число простое, поэтому произведение a1b1c1... только тогда разделится на a, когда одни из его множителей делится на a (теорема 2); но простое число может делиться на другое простое число, отличное от единицы, только тогда, когда эти простые числа одинаковы. Значит, одно из чисел: a1b1c1 ... равняется a. Пусть a1 = a. Разделив обе части равенства на a, получим

bc... = b1c1... .

Подобно предыдущему, убедимся, что один из множителей b1, c1 ... равен b. Пусть b1 = b; тогда cd... = c1d1... Продолжая эти рассуждения далее увидим, что все множители первого ряда входят также и во второй ряд. Разделив обе части равенства на a1 убедимся, что в первом ряду есть множитель a1. Таким образом, подобно предыдущему, найдем, что, все множители второго ряда входят и в первый ряд. Отсюда следует, что оба эти ряда могут отличаться только порядком множителей, а не самими множителями, другими словами, что эти два ряда представляют один и тот же ряд. Иначе говоря, каждое число (кроме единицы) может быть разложено па простые множители и притом только одним способом.

§ 94. Некоторые сведения о простых числах. Легко убедиться, что существует бесчисленное множество простых чисел. Действительно, допустим противное, т. е. что простых чисел конечное число. В таком случае должно существовать наибольшее простое число. Пусть такое число будет a. Чтобы опровергнуть сделанное допущение, вообразим новое число N, составленное по формуле:

N = (2 · 3 · 5 · 7 … a) + 1,

т. е. вообразим такое число N, которое получится, если перемножим все простые числа от 2 до a включительно и к произведению приложим еще единицу. Так как N, очевидно, больше a, и a, согласно предположению, есть наибольшее из простых чисел, то N должно быть числом составным. Но составное число делится на некоторое простое число (§ 93, теорема 1). Следовательно, N делится на некоторое число из ряда: 2, 3, 5, 7, 11, ..., a. Но этого быть не может, так как N есть сумма двух слагаемых, из которых первое (произведение 2 · 3 · 5 … a) делится на всякое число из ряда: 2, 3, 5, ..., a, а второе (1) не делится ни на одно из этих чисел. Значит, наибольшего простого числа не существует; а если нет наибольшего простого числа, то ряд простых чисел бесконечен.

С древнейших времен простые числа были предметом многочисленных исследований. Между прочим, ученые старались отыскать закон составления простых чисел, который дал бы возможность выразить все простые числа одной или несколькими формулами, или старались найти по крайней мере такую формулу, которая хотя бы и не выражала всех простых чисел, но позволяла бы найти произвольно большое простое число. В этом смысле особенно интересна попытка знаменитого французского математика XVII в. Ферма (Fermat). Он нашел, что формула 2n+1 дает простые числа при n, равном 20 = 1, 21 = 2, 22 = 4, 23 = 8. Действительно, при этих значениях показателя и получаются следующие простые числа:

3, 5, 17, 257.

Основываясь на этом наблюдении (и на некоторых соображениях о свойствах чисел), Ферма высказал предположение, что формула 2n+1 должна давать простые числа при всяком n, равном степени 2. Это мнение долгое время не было опровергнуто, ибо никому (до Эйлера) не удавалось указать хотя бы один случай, когда при n, равном степени 2, формула 2n+1 дала бы составное число. Первый опроверг гипотезу Ферма знаменитый Эйлер (XVIII в.), доказав, что при n = 25 = 32 формула 2n+1 дает число, делящееся на 641. Эта ошибка Ферма представляет собой поучительный пример, насколько в математике неприменим метод умозаключения от частного к общему (метод наведения, или индукции).

(При возрастании n выражение 2n+1 дает числа, увеличивающиеся с чрезвычайной быстротой; например, при n = 24 получается число 65537, при n = 25 – число 4294967297. О таких больших числах трудно было решить (при состоянии науки в XVII и XVIII вв.), простые они или составные).

За неимением формул, выражающих все простые числа, является надобность составить эмпирически (опытным путем) ряд последовательных простых чисел от 2 до какого-нибудь определенного большого числа a. Самый простой и вместе с тем самый древний способ составления такого ряда принадлежит александрийскому математику Эратосфену (жившему в III в. до нашей эры). Способ Эратосфена состоит в том, что из ряда натуральных чисел от 2 до a (число, которым желают ограничить ряд) выключают сначала все числа, делящиеся на 2 (кроме 2), потом все числа, делящиеся на 3 (кроме 3). затем все числа, делящиеся на 5, на 7, на 11 (кроме самих этих чисел), и т. д. Это делается очень просто: выписав ряд нечетных чисел от 3 до a, зачеркивают в нем каждое третье число после 3, каждое пятое число после 5, каждое седьмое после 7 и т. д.

В настоящее время имеются таблицы всех последовательных простых чисел меньших 9 000 000.

Если нет под руками выписанного ряда простых чисел, или если данное число N превосходит наибольшее число выписанного ряда, то возникает вопрос: как узнать, будет ли N простое или составное число? Самый простой для этого способ состоит в следующем. Найдя предварительно √N, выписывают все простые числа, меньшие этого корня. Пусть это будут числа:

2, 3, 5, 7, ..., a.

Если N не разделить ни на одно из этих чисел, то можно утверждать не производя дальнейших делений, что N – число простое. Действительно, так как N = √N · √N, то очевидно, что от деления N на числа, большие √N, должны получаться частные, меньших √N; поэтому если бы число N могло разделиться на какое-нибудь число, большее √N, то оно разделилось бы и на число меньшее √N. Когда N велико, то способ этот может оказаться очень утомительным; так, если N > 1 000 000 то √N > 1 000, а имеется 108 простых чисел, меньших 1000; следовательно, для испытания такого числа потребовалось бы иногда до 168 делений. В теории чисел указываются способы, посредством которых можно значительно уменьшить число делений, потребных для испытаний данного числа; но и при этом все-таки вопрос об определении, будет ли данное число простым или составным, представляет иногда и до сего времени огромные затруднения.