Делимость целых чисел

Обозначим через -- совокупность натуральных чисел, а через -- кольцо целых чисел. Термин «кольцо» означает, что мы имеем дело с множеством R, на котором заданы две операции – сложение и умножение, подчиняющиеся следующим аксиомам.

• Сложение и умножение – ассоциативные операции:

• Сложение – коммутативная операция:

• Умножение дистрибутивно относительно сложения:

и

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

• ,

то R называется коммутативным кольцом. Если же дополнительно, имеется единица -- нейтральный элемент относительно умножения

то R называется кольцом с единицей.

Итак, совокупность целых чисел ℤ -- коммутативное кольцо с единицей. Более того, ℤ -- евклидово кольцо, т.е. в нем имеется возможность деления с остатком, отмеченная в предыдущем параграфе. Заметим, что ℤ не единственное евклидово кольцо. Таковым будет и кольцо многочленов, которое будем изучать далее.

ОПРЕДЕЛЕНИЕ. Говорим, что натуральное число n делит число m, если m=nk для подходящего целого числа k. Обозначается это отношение так: . Число произвольной природы кратно числу , если для некоторого целого числа k (включая ноль).

Например, все решения уравнения кратны , но π не может быть делителем, поскольку оно не натурально. Ноль кратен любому числу , а нулю кратно только число 0.

Понятно, что целое m кратно целому n≠ 0 в том и только том случае, когда m mod n =0.

Среди всех натуральных чисел особо выделяются простые числа -- это числа n имеющие ровно два делителя -- единицу и само число n. Вот первые 99 простых чисел:

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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173,179,181,191, 193, 197, 199, 211,223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293,307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523.

Число, не являющееся простым, называется составным. Пусть k -- составное натуральное число. Тогда для некоторых натуральных чисел , больших единицы. При этом получаем: . Число (так же как и ) либо простое, либо составное. Во втором случае снова раскладываем , где p,q>1, и поэтому . В виду уменьшения делителей, этот процесс не может продолжаться бесконечно. Следовательно, в итоге получаем разложение числа в произведение простых чисел. Тот факт, что такое разложение единственно с точностью до перестановки сомножителей мы докажем позже, а пока сформулируем

ОСНОВНАЯ ТЕОРЕМА АРИФМЕТИКИ. Любое натуральное число , большее единицы, разложимо в произведение простых чисел:

Такое разложение единственно.

ТЕОРЕМА 1. Множество простых чисел бесконечно.

Доказательство. Предположим противное: множество простых чисел исчерпывается числами . Образуем число . Это число по основной теореме арифметики имеет простой множитель . Тем самым для какого-либо i. Тогда из соотношений и вытекает, что p делит их разность, т.е. число 1 и, следовательно, . Это противоречие показывает, что предположение о конечности множества простых чисел неверно. Следовательно, верно отрицание этого утверждения, т.е. верно то, что утверждается в формулировке теоремы. □

Как практически решается задача о разложении натурального числа в произведение простых? Для начала надо научиться отличать простые числа от составных. Возьмем число m= 27489. Не трудно догадаться, что оно делится на 3, так как сумма цифр этого числа – 2+7+4+8+9 делится на 3. Получаем m=3⋅ 9163. А далее? Ничего не поделаешь, придется решать задачу лобовым способом: перебирать все простые числа из списка выше по порядку и каждый раз пробовать – делит ли оно 9163 или нет. При этом достаточно перебрать простые числа, не превосходящие корень квадратный из 9163, т.е. 95,7 (это составит неполную первую строку списка простых чисел). Действительно, если m=a⋅ b – составное, то либо a, либо b не превосходят sqr(m). Потрудившись, получим: m=3⋅ 7⋅ 7⋅ 11⋅ 17. Ну, а если взять m=23167837? Трудиться таким же образом не хочется. Поручим это следующему модулю программ (см. файл Делимость целых чисел. xlsm)

Sub Простота() Debug.Print Iprime(99); IsPrime(8747) ’ → 523, Истина End Sub

Sub Разложение() Dim m As Long Dim Список As Collection Set Список = New Collection m = Cells(3, 2) If m = 0 Or Abs(m) = 1 Then Cells(5, 2) = m: Exit Sub If m < 0 Then Cells(5, 2) = "-" Else Cells(5, 2) = "+" s = Int(Sqr(Abs(m))) m = Abs(m) Do Until m = 1 For j = 1 To MaxIndexPrime k = Iprime(j) If m Mod k = 0 Then Список.Add k: m = m / k: Exit For Next If j > MaxIndexPrime And m <= Iprime(MaxIndexPrime) ^ 2 Then Список.Add m: Exit Do If j > MaxIndexPrime And m > Iprime(MaxIndexPrime) ^ 2 Then Список.Add m: MsgBox "Последний множитель не обязан быть простым": Exit Do Loop

' Распечатка результатов For j = 1 To 30 Cells(5, 2 + j) = Nil ’Очистка ячеек Next For j = 1 To Список.Count Cells(5, 2 + j) = Список(j) Next

End Sub

Получим ответ: 23167837=7⋅ 7⋅ 53⋅8 11