Таблица простых чисел

Для составления таблицы простых чисел используем метод, называемый: «Решето Эратосфена». Для этого выписываем целые положительные числа:

1,2, 3,4...п. (*)

Первое простое число 2. Вычеркиваем все составные, кратные двум -4,6,8,..., то есть четные. Далее из оставшегося ряда вычеркиваем все составные числа, кратные трем. Затем кратные 5, кратные 7, и так далее.

Поскольку мы уже доказали, что если п - составное число, то по крайней мере один из его отличных от единицы делителей не превосходит л/п, то вычеркиваем из ряда (*), получается все числа, кратные простым числам меньше числа Vn.

Теорема 2.20

Всякое целое а или взаимно простое с данным простым р, или же делится на р.

Доказательство. Рассмотрим наибольший общий делитель чисел аир. Так как р - простое, то возможны два случая: или (а, р) = 1, или (а, р) = р.

В первом случае аир - взаимно простые, во втором а : р.

Ч.т.д.

Теорема 2.21

Если произведение нескольких сомножителей делится на данное простое р, то, по крайней мере, один из сомножителей делится на р.

Доказательство. Имеем произведение целых • а₂ а_п, и р - простое. В соответствии с теоремой (2.20), каждый из сомножителей либо взаимно прост с р, либо делится на р. Следовательно, если а_г • а₂ • ... • а_п : р, то хотя бы один из а_г,а₂, ...,а_п обязан делится на р.

Ч.т.д.

Основная теорема арифметики

Теорема 2.22

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

Доказательство. Напомним, что в тексте пособия мы рассматриваем только целые неотрицательные, оговорив заранее, что все сказанное справедливо для отрицательных целых. Итак, рассматривая целые, не равные нулю и единице, введем составное число а > 1 и пусть р_± - будет его наименьшим простым делителем. Тогда а = а₁-р₁.

Если а_г также составное, то пусть р₂ его наименьший делитель. И значит а = а_г- р_г.р₂.

Разложение, очевидно, продолжится до тех пор, пока некоторое a_L не станет равным единице.

И так, пусть получено разложение составного а на простые множители:

« = Рі Рп (2.31)

Докажем единственность полученного разложения.

Предположим существования еще одного разложения числа а:

а = <7i Ят (2.32)

но тогда очевидно, что

Pi-P2--Pn=Qi-Q₂--<7m (2.33)

Правая часть равенства (2.33)делится на д_г. Значит, по крайней мере один из сомножителей левой части делится на q_r.

Пусть, например, р_г : д₁₅ но р_г - простое, следовательно, p±=q. Сокращая на р₁ обе части (2.33), получаем,

Рг ' Рз ? • Рп⁼

Далее повторяем те же рассуждения уже к этому равенству и к следующим за этим, до тех пор, пока в левой части не сократятся все сомножители, но равенство 1 = q_n+i ???<]$, при всех q^l невозможно, значит, заключаем, что обязаны сократиться и все q. Что означает, что разложение числа п(2.31) и (2.32) тождественны.

Ч.т.д.

Если в разложении числа а простые множители повторяются, то, обозначая через a і - кратность некоторого множителя p_t, запишем каноническое разложение числа а:

а = р“'-р“²-...р“*. (2.35)

Для доказательства признаков делимости составных чисел, вспомним принципы записи натуральных чисел в десятичной системе счисления (то есть в той, которую мы используем) при помощи десятичных цифр 0,1,2,3,4,5,6,7,8,9.

Цифры, участвующие в записи числа (при рассмотрении числа справа налево) указывают количество единиц, десятков, сотен и так далее. То есть цифра, стоящая на к - том месте, считая справа, означает количество единиц разряда 10^/<-1.

Таким образом, некоторое целое неотрицательное а_т можно записать в виде целого

а_т = q ? 10^m-1 + с₂ ? 10^m-2 +... + +с_т_₁ -10 +с_т, с_1У...с_тЕ {0,1,2...}.(2.36)

Для короткой записи а_т принята запись:

^am⁼ Q^-2 (2.37)

(черту сверху записываем, чтобы не путать с умножением)

Например, запишем каноническое разложение чисел 17820; 10395.

Решение. Запишем несколько простых чисел 2,3,5,7,11,13,.. и разложим каждое из предложенных на простые множители, начиная с меньшего из возможных.

• а)
• 17820
• 8910
• 4455
• 1485
• 495
• 165
• 33
• 11
• 1
• 2
• 2
• 3
• 3
• 3
• 5
• 3

.11

• б)
• 10395 3
• 3465 3
• 1155 3
• 385 5
• 77 7
• 11 U
• 1^

Следовательно, 17820 = 2² ? З⁴ • 5 • 11; 10395 = З³ • 5 ? 7 • 11.