4. Простые числа

Простые числа играют большую роль в математике - по существу они являются «кирпичами», из которых строятся составные числа.

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

Теорема. Любое составное число можно единственным образом представить в виде произведения простых множителей.

Например, запись 110=2511 есть представление числа 110 в виде произведения простых множителей или разложение его на простые множители.

Два разложения числа на простые множители считают одинаковыми, если они отличаются друг от друга лишь порядком множителей. Поэтому представление числа 110 в виде произведения 2511 или произведения 5211 есть, по существу, одно и то же разложение числа 110 на простые множители.

Раскладывая числа на простые множители, используют признаки делимости на 2, 3, 5 и др. Напомним один из способов записи разложения чисел на простые множители. Разложим, например, на множители число 90. Число 90 делится на 2. Значит, 2 есть один из про­стых множителей в разложении числа 90. Разделим 90 на 2. Число 2 запишем справа от знака равенства, а частное 45 - под числом 90. Число 45 делим на простое число 3, получаем 15. Делим 15 на 3, получаем 5. Число 5 - простое, при делении его на 5 получаем 1. Разложение на множители закончено.

90 =2335

45

15

5

1

При разложении числа на простые множители произведение одинаковых множителей представляют в виде степени: 90=23²5; 60=2² 3 5; 72=2³3². Такое разложение числа на простые множители называют каноническим.

Греческий математик - Евклид доказал, что множество простых чисел бесконечно.

Действительно, предположим, что множество простых чисел конечное и исчерпывается числами 2, 3, 5, 7, ...,р, где p - самое большое простое число. Перемножим все простые числа и их произведение обозначим через а. Прибавим к этому числу 1. Каким будет полученное число а + 1 - простым или составным?

Простым число а+1 быть не может, потому что оно больше само­го большого простого числа, а по предположению таких простых чисел не существует. Но составным оно тоже быть не может: если а+1 составное, то оно должно иметь хотя бы один простой делитель q. Так как число а = 235 ...р также делится на это простое число q, то и разность (а + 1) - а, т.е. число 1, делится на q, что невозможно.

Итак, число а не является ни простым, ни составным, но этого тоже не может быть - всякое число, отличное от 1, либо простое, либо составное. Следовательно, наше предположение о том, что множество простых чисел конечное и есть самое большое простое число, неверно, и значит, множество простых чисел бесконечное.

5. Способы нахождения наибольшего общего делителя и наименьшего общего кратного чисел

Рассмотрим сначала способ, основанный на разложении данных чисел на простые множители.

Пусть даны два числа 3600 и 288. Представим их в каноническом виде: 3600 = 2⁴3²5²; 288 = 2⁵3². Найдем наибольший общий делитель данных чисел. В его разложение должны войти все общие простые множители, которые содержатся в разложениях чисел 3600 и 288, причем каждый из них нужно взять с наименьшим показателем, с каким он входит в оба разложения. Следовательно, D (3600, 288) = 2⁴3² = 144.

Вообще, чтобы найти наибольший общий делитель данных чисел:

1) представляют каждое данное число в каноническом виде;

2) образуют произведение общих для всех данных чисел простых множителей, каждый с наименьшим показателем, каким он входит во все разложения данных чисел;

3) находят значение этого произведения - оно и будет наибольшим общим делителем данных чисел.

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

K(3600, 288) = 2⁵3²5 = 7200.

Вообще, чтобы найти наименьшее общее кратное данных чисел:

1) представляют каждое данное число в каноническом виде;

2) образуют произведение всех простых множителей, находящихся в разложениях данных чисел, каждый с наибольшим показателем, с каким он входит во все разложения данных чисел;

3) находят значения этого произведения, оно и будет наименьшим общим кратным данных чисел.

Задача 1. Найти наибольший общий делитель и наименьшее об­щее кратное чисел 60, 252 и 264.

Решение. Представим каждое число в каноническом виде: 60=2²35, 252=2²3²7, 264=2³311.

Чтобы найти наибольший общий делитель данных чисел, образуем произведение общих для всех данных разложений простых множителей, каждый с наименьшим показателем, с каким он входит во все решения данных чисел: D(60,252,264)=2²3=12.

Наименьшее общее кратное чисел можно найти, образовав произве­дение всех простых множителей, находящихся в данных разложениях, каждый с наибольшим показателем, с каким он входит во все разложе­ния данных чисел, т.е. K(60, 252, 264)=2³3²5711=27720.

Задача 2. Найти наибольший общий делитель и наименьшее общее кратное чисел 48 и 245.

Решение. Представим каждое число в каноническом виде: 48=2⁴3, 245=57².

Так как разложения данных чисел не содержат общих простых множителей, то D(48, 245) = 1, а K(48, 245)=48245=10760.

Отыскание наибольшего общего делителя двух натуральных чисел по их каноническому виду требует предварительного разложения чисел на простые множители. Это несложно сделать, если числа не велики, но для многозначных чисел найти их каноническое разложение быва­ет трудно. Существует способ отыскания наибольшего общего делителя, требующий лишь деления с остатком. Этот способ был предложен Евклидом, и его называют алгоритмом Евклида. Он основан на следующих трех утверждениях, доказательство которых мы опускаем:

1. Если а делится на b, то D (а, b) = b.

2. Если а = bq+r и r<b,то множество общих делителей чисел а и b совпадает с множеством общих делителей чисел b и r.

3. Если а=bq+r и r<b, то D(а, b) = D(b, r).

Сформулируем теперь алгоритм Евклида для нахождения наиболь­шего общего делителя натуральных чисел а и b.

Пусть а>b.

Если а делится на b, то D(а, b) = b.

Если при делении а на b, получается остаток r, то a = bq+r и D(а, b) = D(b, r) и задача свелась к отысканию наибольшего общего делителя чисел b и r.

Если b делится на r, то D(b, r) = r и тогда D(а, b) = r.

Если при делении b на r получается остаток r, , то b = rq₁+r₁ и поэтому D(r,r₁) = D(b,r) = D(а,b).

Продолжая описанный процесс, получаем все меньшие и меньшие остатки. В конце концов получим остаток, на который будет делиться предыдущий остаток. Этот наименьший, отличный от нуля, остаток и будет наибольшим общим делителем чисел а и А.

Найдем при помощи алгоритма Евклида наибольший общий дели­тель чисел 2585 и 7975. Процесс последовательного деления будем записывать так:

_ 7975 2585

7755 3 975 = 2585 3 + 220.

_ 2585 220

220 11 2585 = 220  11 + 165

_ 385

220

_220 165

165 1 220 = 165  1 + 55

_ 165 55

165 3 165 = 55  3 + 0

0

В последнем случае остаток равен нулю. Значит, D (7975, 2585) = 55.