Лекция 3

Тема 1. Теория делимости

1. Простые и составные числа.

Продолжим изучение свойств делимости целых положительных чисел.

Всякое целое, большее 1, то есть всякое натуральное число, отличное от 1 имеет, по крайней мере, два делителя: 1 и самого себя.

Число 1 имеет только один положительный делитель, как-то 1. В этом отношении число 1 в ряде натуральных чисел стоит целиком особо.

Определение. Целое число p, большее 1, которое не имеет, кроме 1 и p других положительных делителей называется простым. Число называют составным, если оно имеет делители отличные от 1 и a.

Простыми будут, например, числа 2, 11, 13; числа 4, 9, 21  составные. Число 1 не принадлежит ни к простым числам, ни к составным.

Докажем несколько важных теорем о простых числах.

Теорема 1. Любое положительное целое (натуральное) число а или делится на данное простое число p, или взаимно простое с p.

Д е й с т в и т е л ь н о, наибольший общий делитель (a, p), должен быть делителем простого числа p, и потому равняется или p или 1. В первом случае a делится на p, во втором  a и p взаимно простые числа.

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

Д е й с т в и т е л ь н о, из предыдущей теоремы вытекает, что каждый из сомножителей или взаимно простой с p, или делится на p. Но если бы все сомножители были бы взаимно простые с p, то по теореме 7, Л-2 (если каждое из чисел a₁,a₂,...,a_m взаимно простое с b₁,b₂,...,b_n, то и произведение a₁a₂a_m взаимно простое с произведением b₁b₂b_n) и их произведение было бы взаимно простым с p. Поэтому хотя бы один из сомножителей делится на p.

Теорема 3. Наименьший отличный от нуля делитель целого числа, большего 1, есть число простое.

Д е й с т в и т е л ь н о, пусть q  отличный от 1 наименьший делитель целого числа a, большего 1, то есть a = qa₁. Если бы q было составным, то оно имело бы некоторый делитель q₁ такой что 1 < q₁ < q, причем число a, делясь на q, должно было бы по свойству делимости 4, Л-1 (если a кратно b, и при этом b кратно c, то a кратно с) делится и на q₁. А это противоречит нашему предположению, что q наименьший делитель числа a. Итак, q  простое.

Теорема 4. Наименьший отличный от единицы делитель составного числа a не больше, чем число .

Д е й с т в и т е л ь н о, пусть отличным от 1 наименьшим делителем числа a есть q. Тогда a = qa₁, где a₁  некоторое натуральное число, причем a₁  q, так как в противном случае q не было бы наименьшим положительным делителем числа a. Домножив обе части неравенства на одно и то же число a = qa₁, получим aa₁  q a₁q, откуда и вытекает, что a  q², или q < .

Теорема 5. (Евклида) Множество простых чисел бесконечно.

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

Целое число p > 1, поэтому, по теореме 3 (наименьший отличный от нуля делитель целого числа, большего 1, есть число простое) оно или простое или делится на простое число q, отличное от каждого из чисел . Отсюда вытекает, что существует по крайней мере, еще одно простое число, отличное от чисел , а это противоречит нашему предположению. Итак, наше предположение неверное.

Для построения таблицы простых чисел, которые не превышают данного целого числа N, существует простой способ, называемый решетом Ератосфена¹. Он состоит в следующем.

Выписываются подряд все натуральные числа от 2 до N

2, 3, 4, 5, . . . , N. (1)

Потом в этом ряде вычеркиваются все числа, кратные 2, кроме самого числа 2. Первым по счету, который остается в этом ряде после вычеркиваний и самого числа 2, будет число 3. Число 3 не делится на 2, так как в противном случае мы бы его вычеркнули. Итак, число 3 делится только на 1 и на самого себя, и потому оно простое. Теперь в ряде (1) зачеркиваются все числа, кратные 3, кроме самого числа 3. Очередным числом, которое останется в ряде (1), будет число 5. Оно не делится ни на 2, ни на 3, ни на 4, а делится только на 1 и на самого себя, поэтому оно также простое. Дале в ряде, который остался, зачеркиваются все числа кратные 5 и т.д. Когда указанным способом уже вычеркнутые все числа, кратные простым, меньшие чем , то все не вычеркнутые меньшие N, будут простыми. Действительно, всякое составное число a, меньше N, уже вычеркнуто, как кратное его простого наименьшего делителя, который по теореме 4 (наименьший отличный от единицы делитель составного числа a не больше, чем число ) меньше или равняется .

Из изложенного вытекает:

1. Приступая к вычеркиванию кратных простого числа p, это вычеркивание следует начинать с p².

2. Упорядочение таблицы простых чисел, которые не превышают N, закончено, как только вычеркнуты все составные, кратные простым, которые не превосходят .

Докажем теперь теорему, которая играет фундаментальную роль как в теории делимости, так и во всей теории чисел. Ее называют основной теоремой арифметики.

Теорема 6. Каждое отличное от 1 натуральное число можно записать в виде произведения простых чисел и причем единственным способом, если не принимать во внимание порядок размещения сомножителей (всякое целое, большее 1, раскладывается в произведение простых сомножителей).

Д е й с т в и т е л ь н о, пусть a  целое число, большее 1. Обозначив буквой его наименьший простой делитель, по теореме 1 (любое положительное целое число а или делится на данное простое число p, или взаимно простое с p) имеем a = p a . Если a > 1, то, обозначив буквой его наименьший простой делитель, имеем . Если a > 1, то подобно предыдущему, находим и т.д., пока не прийдем к какомунибудь числу a , которое равняется 1, и,следовательно, тогда . Подставляя каждое следующее равенство в предыдущее, получим разложение числа a на простые сомножители:

. (2)

Докажем, что представление (2) единственное. Предположим, что для того же самого числа a существует и второе разложение на простые сомножители, скажем, a = q q  q . Тогда можем записать p p  p = q q  q .

Правая часть этого равенства делится на q . Тогда, по теореме 2 (если произведение нескольких натуральных чисел делится на простое число p, то по крайней мере, один из сомножителей делится на p), по крайней мере один из сомножителей левой части должен делиться на q . Пусть, например, p делится на q (порядок размещения сомножителей в нашем распоряжении). Тогда p = q , так как p , кроме 1, делится только на p . Сократив обе части равенства на p = q , получим p  p = q  q .

Повторив предыдущие соображения относительно этого равенства, приходим к результату p p  p = q q  q и т.д., пока, в конце концов, в одной части равенства, например, в левой не сократятся все сомножители. Но одновременно должны сократиться все сомножители правой части, так как равенство , при , которые превышают 1, невозможно. Таким образом, второе разложение на простые сомножители тождественно первому.