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