Факторизация Целых Чисел
Целью данной статьи является предоставление читателю всей необходимой информации про факторизацию целых чисел для ее дальнейшего использования в барах со знакомыми программистами и математиками.
Почему это важно?
В современной криптографии активно используется алгоритм шифрования RSA. RSA сам по себе не является практически надежным (semantically secured), так как при одних и тех же значениях входных параметров (ключа и сообщения) выдаёт одинаковый результат. Однако, его удобно использовать как вспомогательный алгоритм, для шфровки, например, сеансового ключа (используется в TLS, а так же в ранних версиях PGP). Несложно показать, что задача дешифровки сообщения или ключа, зашифрованного с помощью RSA сводится к проблеме факторизации целых чисел.
Disclaimer
Есть отличная статья Connelly Barnes «Integer Factorization Algorithms». Эта статья является не прямым переводом той, с некоторыми дополнениями и исключая код и доказательства.
Матчасть
Немножко сведений из институсткого курса по математике для более глубокого понимания задачи:
Основная теорема арифметики
Любое натуральное число больше единицы можно разложить в виде произведения k простых чисел. Например . Теперь рассмотрим число
(Warning) Огромное число
Это число известно как RSA-2048. В Марте 1991 года RSA Laboratories предлжили приз в 200,000$ тому что сможет его факторизовать. На данный момент его не факторизовали. Для сравнения: последнее факторизованное число из RSA Factoring Challange — RSA-250:
(Warning) Еще одно огромное число
Оно имеет на 367 цифр в записи меньше чем RSA-2048. Его разложили с помощью Number Field Sieve algorithm (GNFS) задействовав 2700 CPU ядер-лет используя 2.1GHz Intel Xeon Gold 6130 CPU.
Вспомогательная теорема
Пусть у числ есть два натуральных делителя: .Тогда младший из них .
Теорема полезна для ограничения количества итераций в алгоритмах факторизации, а также оценки их сложности. У этой теоремы простое и красивое докозательство:
Если , то . Тогда , то есть , а это не возможно.
Открытая проблема математики
На данный момент в теории сложности вычеслений стоит открытый вопрос: «Принождежит ли факторизация целых чисел классу сложности P?». В более простых терминах: Можно ли найти делитель числа N меньше чем любое на перед заданное число за количество шагов , где — количество цифр , — многочлен о. Другими словами, ответ на вопрос: «Какой самый быстрый алгоритм факторизации?» еще не найден.
Алгоритмы факторизации чисел
Мы будем рассматривать следующие алгоритмы:
Перебор делителей (Trial Division)
Метод Ферма (Fermat Factorization)
ро-алгоритм Полларда (Pollard rho Factorization)
Метод Брента (Brent’s Factorization Method)
p-1 алгоритм факторизации Полларда (Pollard p-1 Factorization)
Нужно отметить, что все эти алгоритмы ставят себе целью не разложить число на все простые множители, а только найти числа , так как если мы смогли это сделать, можем сделать то же самое для и , что является более простой задачей.
Перебор Делителей
Перебор делителей — простейший алгоритм факторизации. Будем смотреть является ли числ натуральным для всех s начиная с 2 и до .
Сложность этого алгоритма — или в зависимости от того, гоняем ли мы алгоритм по всем числам или только по простым.
Метод Ферма
Метод был предложен в 1600 году. Он основывается на формуле . Тогда вместо чисел мы ищем числа . Числа x и y обязательно целые, так как сумма и разность нечетных чисел — четное число, а и (если p или s четные, то сразу можем решить задачу: s = 2).
К тому же, и , а следовательно . Тогда алгоритм выглядит так: Последовательно проверяем, является ли число квадратом целого числа для всех x от до .
Сложность алгоритма в худшем случае . У этого алгоритма есть ряд улучшений — оптимизация методом перебора делителей, метод решета, Крайчика-Ферма и др.
Ро-алгоритм Полларда
Теперь подходим к более менее современным алгоритмам: Ро-алгоритм Полларда был предложен в 1975 году. Он основан на следующей последовательности:
Видно, что последовательность переодична и период , так как все берется по модулю N. Можно показать, что если мы найдем , то — делитель N. gcd — наибольший общий делитель.
Причем это справедливо для любой последовательности с модулем N. В статье Weisstein, Eric W. «Pollard Rho Factorization.» показано, что ожидаемый период пропорционален почти для всех N. Это одна из причин использования именно такой.
Есть также другие варианты задания последовательности: например или .
Так как s мы не знаем, Поллард предложил сравнивать и . Таким образом, алгоритм состоит в последовательной проверке всех n на то, что является нетривиальным делителем N. Сложность такого алгоритма — .
Метод Брента
В 1980 году Ричард Брент опубликовал статью «An improved Monte Carlo factorization algorithm», в которой предложил улучшение ро-алгоритма Полларда.
Отличие заключается в том, что вместо мы ищем делитель в виде , где m — наибольшее целое число удвлетворяющее .
Последовательность тоже задается по другому:
Как и в алгоритме Полларда существуют и другие различные варианты задания такой последовательности. Результатом такого улучшение стало уменьшение сложности: .
p-1 алгоритм факторизации Полларда
В 1974 году Поллард опубликовал еще один алгоритм. Он основан на малой теореме Ферма:
Если p — простое число, являющееся делителем натурального числа a, то .
Для понимания алгоритма нужно сделать еще один математический шаг: пусть есть число , такое что — делитель . Можем переписать как по свойству факториала. Таким образом: . Получаем, что — делитель . Мы можем искать делитель в виде , в этом и состоит алгоритм.
В данном случае сложно явно определить сложность не вдаваясь в сложную математику, но условно сложность можно записать как .
Сравнение производительности алгоритмов
Следующий график показывает количество итераций разных алгоритмов для N разного порядка:
Производительность алгоритмов факторизации
Вывод
На графике видно, что факторизация чисел порядка требует порядка 1000 итераций. Нахождение нового, еще более производительного алгоритма не только может заработать создателю 200,000$, но и, быть может, позволит ему взломать современные алгоритмы шифрования, а следовательно, улучшить их.
Е25.3. имеющие ровно три нетривиальных делителя
имеющие ровно три нетривиальных делителя. Назовём нетривиальным делителем натурального числа его делитель, не равный единице и самому числу. Например, у числа 6 есть два нетривиальных делителя: 2 и 3. Найдите все натуральные числа, принадлежащие отрезку [123456789; 223456789] и имеющие ровно три нетривиальных делителя. Для каждого найденного числа запишите в ответе его наибольший нетривиальный делитель. Ответы расположите в порядке возрастания.
Факторизация чисел и сумма неизвестных делителей. Часть IV
и более цифр, эта возможность, а точнее задача не получила приемлемого для практики (за обозримое время) решения до наших дней. Кратко эту задачу называют задачей факторизации больших чисел(ЗФБЧ). Ее формулировка проста и известна уже несколько тысячелетий: для заданного натурального числа N = pq найти все его нетривиальные делители.
При заданном значении СННЧ N что можно узнать о его делителях? Практически ни о числе, ни составе делителей в теории чисел нет теорем. Поэтому ЗФБЧ до сегодняшнего дня является практически нерешаемой. Известен переборный алгоритм решения ЗФБЧ методом решета о котором мной написаны прочие статьи цикла под спойлером. Имеется зацепка в виде суммы σ(N) = N +p +q +1 делителей N для подступа к ее решению, минуя решета и связанные с ними проблемы.
Так в Г 2± – модели НРЧ в клетке (
) всегда лежит сумма делителей N, если само число N помещено в клетке (
). Кроме этого, в клетке (
) лежит значение функции Эйлера СННЧ N, если его собственные делители простые числа.
В теории чисел известны две формы представления (моделей) числа: аддитивная и мультипликативная на основе ОТА. Эти формы (при аддитивном представлении числа суммой членов отрезка непрерывной последовательности нечетных чисел) тесно связаны. Число слагаемых в сумме равно меньшему делителю, а среднее слагаемое — большему. Это не так, если аддитивная форма представляет произвольное разбиение числа на части. Например, в 1-ом случае 105 =33+35+37 =3·35 и 105 = 60+40 +5 ≠3·40 — во 2-ом.
Поводом для написания этой работы послужило стремление автора познакомить читателей с подходом к задаче факторизации чисел на основе факта, открытого автором при изучении модели натурального ряда чисел (НРЧ), а также с результатом Л. Эйлера,
, который состоит в том, что для произвольного СННЧ N можно вычислить сумму σ(N) его делителей, не располагая значениями самих делителей. Это положение граничит с мистикой, но оказывается такое возможно при наличии качественных моделей НРЧ и отдельного числа.
Определенным стимулом явилась также публикация Пшеннова А.В. в Интернете, где приводится некоторый фактический материал по делителям чисел и их суммам. Конечно,
основной причиной является наблюдение, сделанное автором самостоятельно, при изучении созданной и разрабатываемой им оригинальной модели натурального ряда чисел (НРЧ). Приведу краткое описание модели, которая ранее уже рассматривалась здесь .
Таблица М — Модель (плоскостная) натурального ряда чисел 
символами
в модели обозначены соответственно номера строк и столбцов.
В модели использовано известное положение о том, что в любой клетке СННЧ N = а·b представимо разностью квадратов двух целых чисел (
) разной четности, которые выбираются специальным образом, т.е.
и а, b играют роль диагоналей, пересекающихся в этой клетке модели.
Сущность наблюдения в Г 2± – модели НРЧ (таблица М) состоит в следующем. Располагая в модели координатами клетки, легко определяются значения чисел в них, но обратная задача трудно решаемая. Допускаем, что координаты клетки заданного СННЧ N известны.
Сумму делителей числа N из клетки (
) обозначают σ(N). Cумма σ(N) этих двух (а, b) неизвестных нетривиальных делителей, а также тривиальных делителей 1 и самого N, определяется (вычисляется) в модели, как значение числа в другой клетке с координатами (
), в то время как само число N помещается в клетке (
), что легко показывается. Установлены, сформулированы и доказаны две новые теоремы.
Теорема 1. Если в клетке (
) Г 2± – модели НРЧ содержится СННЧ N = а·b, где а,b -собственные делители играют роль номеров короткой и длинной диагоналей, пересекающихся в этой клетке, то в строке ниже под этой клеткой в клетке (
) содержится сумма σ(N) делителей СННЧ N. (положение N задано, а и b неизвестны).
Доказательство. Значение любой клетки Г 2± – модели НРЧ по основному соотношению модели равно
, где в скобках соответственно приведено произведение
— номеров диагоналей длинной и короткой, пересекающихся в этой клетке и выполняющих роль делителей N=аb. Под клеткой со значением N помещается клетка, значение в которой равно произведению диагоналей, увеличенных на 1, т.е. (а+1)(b+1)=а·b+а+b+1=σ(N), раскрывая скобки, получаем сумму делителей. Этим доказательство завершается.
В этом равенстве а·b+1=N+1, а разность σ(N)-N-1=а+b — есть сумма только собственных делителей N. Названные зависимости легко могут быть выражены через переменные модели (
.
Здесь же отметим и еще одно наблюдение для которого справедлива следующая
Теорема 2. Если в клетке (
) Г 2± – модели НРЧ содержится СННЧ N = а·b, где а,b -собственные делители играют роль номеров короткой и длинной диагоналей, пересекающихся в этой клетке и являющиеся простыми нечетными числами, то в строке выше над этой клеткой в клетке (
) содержится функция Эйлера φ(N) СННЧ N. Положение N задано, а и b неизвестны.
Доказательство. Здесь повторяется положение предыдущей теоремы, но для клетки выше изменяются знаки. Над клеткой со значением N помещается клетка, значение в которой произведение номеров диагоналей, уменьшенных на 1, т.е. φ(N)=(а-1)(b-1) = а·b -а-b+1. Этим равенством доказательство теоремы завершено.
Результаты обеих теорем (показано ниже) могут быть применены в атаках на шифр RSA.
Из второй теоремы следует, если а и b простые нечетные числа-нетривиальные делители числа N, то произведение φ(N) = (а – 1)( b – 1) и разность
являются теоретико-числовой функцией Эйлера для составного числа N.
Приведем вид решетчатой функции σ(N) суммы делителей в зависимости от числа N. По оси ординат расположим числа N, а по оси абсцисс σ(N) сумму их делителей (1≤N≤1000). 
На графике отчётливо просматриваются несколько наклонных линий из точек, имеющих сходство с прямыми, например, нижняя линия соответствует суммам делителей простых чисел. Верхняя граница – это наиболее сложные числа (имеющие наибольшее количество делителей) — это не прямая, но и не парабола. Возможно – это показательная функция вида (
При решении задачи факторизации совсем не обязательно сразу получать все степени простых чисел. Можно пойти путем нахождения вначале лишь одного единственного делителя (второй получается, как частное при выполнении деления). Этот единственный делитель может быть и составным числом, как впрочем, и частное от деления числа N на него. После этого оба найденные делителя (числа меньшей разрядности) подвергаются процедуре дальнейшей факторизации до ее полного завершения.
Процесс продолжается до тех пор, пока это оказывается возможным. Как только все возможности разложения всех делителей N исчерпаны, процесс факторизации прекращается. Найденные простые факторы можно перемножить между собой, что должно дать в результате вновь исходное число N.
Этот факт служит подтверждением правильности найденного решения.
Чтобы количественно почувствовать и оценить зависимость σ(N) – суммы делителей от числа N покажем последовательность таких сумм для первых ста натуральных чисел N (см. таблицу 1):
Таблица 1. Суммы σ(N) делителей натуральных чисел, полученные Эйлером. 
Из приведенных весьма ограниченных данных видим, что для простых чисел σ(N)=N+1, что некоторые различные числа (46, 55, 71) имеют совпадающие значения σ(N) = 72, а некоторые N не являются суммами делителей ни одного из натуральных чисел.
В теории чисел известны следующие результаты. Найти сумму всех делителей натурального числа можно с использованием канонического разложения N, если оно известно. Легко найти простым перебором σ(N) для небольших натуральных чисел, например,
Но при достаточно больших значениях N нахождение всех делителей, а тем более их суммы становится затруднительным. Совсем другое дело, если уже известно, каноническое разложение числа N.
Делителями N являются все числа, для которых
$inline$0 ≤ β_s ≤ α_s , s = 1(1)k$inline$
. Ясно, что σ(N) представляет собой сумму всех таких чисел при различных значениях показателей
В работе предлагается один из возможных вариантов построения алгоритма решения за-дачи факторизации, который не зависит или слабо зависит от разрядности факторизуемого числа. В основу алгоритма поиска решения положен принцип использования суммы двух нетривиальных делителей (факторов) натурального числа.
Ясно, что существуют составные натуральные числа, образованные произведением всего лишь двух простых чисел (RSA числа). Это, вообще говоря, частный для теории чисел случай, но очень важный для практики. В общем случае оба делителя а и b – составные числа. Для лучшего понимания идеи такого алгоритма факторизации ниже приведем числовые примеры, рассматриваемые в рамках приведенной Г 2± – модели НРЧ (табл. М).
Пример 1.
Найти разложение заданного составного натурального числа N на множители а и b, если а и b неизвестны, а их сумма σ(N)=а + b известна.
Данная задача может быть сведена к нахождению решения системы двух алгебраических уравнений с двумя неизвестными. Чтобы исключить тривиальные решения (делители) вычтем их из заданной σ(N) суммы делителей
В рассматриваемом примере решением задачи факторизации числа N являются значения а и b, удовлетворяющие замкнутой системе двух алгебраических уравнений:
Здесь σ(N) обозначает сумму всех делителей N, которая полагается известной, а
вычисляется и представляет собой сумму лишь двух нетривиальных делителей простых или составных чисел. Как находить значения таких сумм σ(N) и
будет показано позже.
Выполним преобразование записанной системы двух уравнений путем исключения переменной b. Это приводит к одному квадратному уравнению
, корни которого и есть искомые делители числа N. Воспользуемся теоремой Виета. Тогда корни квадратного уравнения определяются соотношением 
Таким образом, задача факторизации числа в рассматриваемой ситуации будет успешно решена, если для числа N предварительно будет определена σ(N) сумма делителей.
Пример 2 (числовой с двумя простыми делителями). Задано N = a·b = 301, для которого известна клетка (
) его размещения в Г 2± – модели НРЧ. Требуется определить cумму всех делителей σ(N) числа N, вычислить функцию Эйлера и факторизовать N.
Решение. Воспользуемся результатом Эйлера для подсчета суммы собственных делителей
Уже отмечалось, что для простого числа q сумма σ(q)=q+1 равна сумме делителей q и 1. Поэтому при
$inline$N = 301 =7·43, σ(301)=σ(7)·σ(43)=8·44 =352 $inline$
Располагая моделью Г 2± этот результат получается вычислением в одной клетке. Находим
, сумма неизвестных а и b делителей
$inline$а_<1,2>=50/2±(25^2-301)^ ½ =25± 18; а = а_1=43, b=а_2 =7.$inline$
Покажем как связаны делители и координаты клетки
Наконец, вычислим значение функции Эйлера
Ответ: корни уравнения-делители N
реализуют факторизацию. Проверка N = a∙b = 43∙7 = 301,
Убедимся, что в терминах переменных
сумма делителей совпадает с вычисленной
Вычислим при найденных значениях a и b,
. Значения функции Эйлера, вычисленные двумя способами, совпали.
Пример 3 (числовой с одним простым и одним составным делителем). Задано N = 147, для которого сумма всех делителей σ(N) = σ(147) = 1+3+7+21+49 +147= 228. Но для четырех делителей числа N сумма равна 1 + а + b + 147, σ(N) = 176. Здесь а=21 и b=7 неизвестные делители, формирующие значение N. Требуется факторизовать число N.
$inline$а_<1,2>=28/2 ±(196 — 147)^ ½= 14 ± 7.$inline$
Установим связь корней с
.
Ответ: Корни уравнения
. Проверка a∙b = 21∙7 = 147
В этом примере один из делителей а=21 оказался составным числом, но именно это число и является слагаемым в сумме делителей, что видим в модели (табл. М строки 14,15; столб. 7)
В примерах 2 и 3 рассмотрены задачи, в которых в качестве исходных данных задано число N и клетка его размещения. Требовалось факторизовать число N, т.е. отыскать делители. Для факторизации привлекалась модель НРЧ и в ее клетках отыскивалась сумма делителей σ(N) и функция Эйлера φ(N), когда делителей (собственных) было всего два и они оба были простыми числами.
Существует симметричная относительно исходных данных задача, в которой известна сумма N+1 кратных делителей N = pq
и клетка в Г 2± – модели НРЧ с координатами (
), в которой лежит кратное целому числу sN произведение
. Само число N лежит в последней клетке строки x1 с кратным произведением в Г 2- – модели НРЧ. Требуется факторизовать составное число N.
Пример 4. Заданы составное число N=pq =77, сумма
, коэффициенты целые числа, координаты клетки (
) с кратным произведением числа
. Требуется факторизовать N, т.е. определить p и q делители N.
Решение. По координатам клетки легко определяется значение в ней
. Далее определяем произведение коэффициентов делителей в сумме
. Получаем для двух неизвестных p и q замкнутую систему из двух уравнений:
.
Введем новые обозначения неизвестных
.
Последнее слагаемое в квадратном уравнении необходимо сделать квадратом числа 39. Для этого добавим в левую и правую части уравнения число
Пример 5. Если
– различные простые числа, то σ(N) для различных их комбинаций имеет формулы:
Пользуясь этими соотношениями, можно записать
$inline$σ(a^q·b^w·c^e·d^r) = σ(a^q)·σ(b^w)·σ(c^e)·σ(d^r). $inline$
по формуле конечного числа членов геометрической прогрессии приходим к равенству 
Следующий результат в виде ряда для σ(N) получил Л. Эйлер, который записал сомножители N в многочленном представлении и раскрыл скобки в произведении многочленов
Ряд Эйлера
Этот ряд обеспечивает вычисление суммы делителей составного числа N, не зная ни числа делителей, ни их значений.
Аналогичный результат получен в рамках исследования Г 2± – модели НРЧ (Теоремы 1 и 2)
Пример 6. Необходимо вычислить σ(360), при известном каноническом разложении на множители числа. По формулам теории чисел это легко вычисляется.
Эта задача по формулам не решается, если для N отсутствует каноническое разложение.
Ряд Эйлера позволяет свести задачу к решению системы алгебраических уравнений как в примерах 2 и 3. Но возникает ряд проблем, хотя и преодолимых. Привлечение модели НРЧ (табл. М) снимает часть затруднений, но создает свои.
Описание и использование ряда Эйлера при расчетах σ(N)
Пусть задано нечетное число N, которое требуется факторизовать, и известно, что N = pq, где p и q простые числа. Делителями N кроме p и q являются также 1 и само число N. Если известна сумма p + q = σ(N), то, как показано ранее, задача факторизации легко решается. Далее поясним как находятся значения σ(N) без знания делителей.
Рассмотрим две числовые последовательности: а) натуральных чисел;
б) нечетных чисел.
а)1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 3738…
б) 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49……
вторая последовательность начинается не 1, а числом 3.
Сольем эти две последовательности в одну, обозначив ее s, чередуя числа из последовательностей а) и б), а также выполним нумерацию элементов s сформированного ряда.
Таблица 2 – Совмещенные последовательности ряда нечетных и натуральных чисел. 
Нечетные номера получают элементы из натурального ряда, а четные – из ряда нечетных чисел (при начале отсчета элементов s от единицы и наоборот, если начать отсчет номеров от нуля).
Использование ряда s предполагает возможность вычисления любого его элемента по текущему номеру или восстановление текущего номера по известному значению элемента ряда. Анализ ряда s показывает, что для элементов нечетного ряда их значение на единицу больше текущего номера, а значения элементов из натурального ряда равны половине увеличенного на единицу порядкового номера. Следующие примеры проясняют эти утверждения.
Пример 7. Порядковый номер элемента ряда s равен 30. Определить значение s(30).
Так как 30 ≡ 0(mod2), т.е. номер – четное число, то s(30) принадлежит ряду б) нечетных чисел и равно s(30) = 30 + 1 = 31.
Пример 8. Порядковый номер элемента ряда s равен 37. Определить значение s(37).
Определяем четность номера 37 ≡ 1(mod2). Номер нечетный, следовательно, число с этим номером принадлежит натуральному ряду а) и его значение
s(37) = (37 + 1)/2 = 19.
При известном значении s можно определить его порядковый номер. Необходимо только учесть одну особенность ряда s. Нечетные значения в ряде s встречаются дважды и, следовательно, занимают в нем две позиции с разными номерами. Поэтому для нечетных s существуют два порядковых номера, которые требуется определять (находить).
Пример 9. Значение элемента ряда s = 13. Определить порядковые номера для s-1(13).
Если s принадлежит натуральному ряду чисел, то его номер является нечетным числом и большим из двух возможных.
Таким образом, №натур(s) = 2s – 1 = 2∙13 – 1 = 25.
Если s принадлежит ряду нечетных чисел, то его номер – четное число и определяется по формуле № нечетн(s) = s – 1 = 13 – 1 = 12. Это меньший номер из двух. Оба номера связаны простым соотношением
№натур(s) – № нечетн(s) = (2s – 1) – (s –1)= s = 25 – 12 = 13.
Разность номеров равна значению s. Таким образом, поведение элементов ряда s, т.е. значения и занимаемые позиции устанавливаются достаточно простыми соотношениями.
Как этими фактами можно воспользоваться при решении задачи факторизации?
Оказывается, ряд s является рядом разностей смежных элементов другого ряда k(i), открытого Эйлером, и по известному ряду s ряд k(i) можно восстановить.
Таблица 3 – Последовательность нумерованных чисел k(i) ряда Эйлера 
k(1) =1, k(2) = k(1) + s(1) = 2, k(3) = k(2) + s(2) = 2 + 3 = 5,
k(4) = k(3) + s(3) = 5 + 2 = 7, k(5) = k(4) + s(4) = 7 + 5 = 12 и т. д… в общем виде
k(i + 1) = k(i) + s(i), i = 1(1)…, k(1) = 1.
Ряд k(i) был открыт Л. Эйлером, который указал на его применимость к решению задачи определения сумм делителей натуральных чисел в формуле:
σ(N)=σ(N-k(1))+σ(N-k(2))-σ(N-k(3))-σ(N-k(4))+σ(N-k(5))+σ(N-k(6))-σ(N-k(7))-
-σ(N–k(8))+= … = σ(N-1)+σ(N-2)-σ(N-5)-σ(N-7)+σ(N-12)+σ(N-15)-σ(N-22)-σ(N–26)+ …
При выполнении расчетов σ(N) для аргумента функции σ(N) вычисляются разности
N — k(i), если σ(N) обозначает любой член этой последовательности, а σ(N — 1),
σ(N — 2), σ(N — 5)… предшествующие члены, то σ(N) всегда можно получить по нескольким предыдущим членам:
σ(N)= σ(N — 1)+ σ(N — 2)- σ(N — 5)- σ(N — 7)+ σ(N — 12)+σ(N — 15)- σ(N — 22)- σ(N – 26)+ …
Знаки «+» и «–» в правой части формулы попарно чередуются.
Возникают еще вопросы. Когда необходимо ограничить бесконечный ряд, остановиться? Как определить значение в точке останова?
Остановка происходит при получении отрицательного или нулевого значения аргумента в некотором слагаемом. Последняя разность при вычислениях N — k(i) может оказаться отрицательной при N Вчера в 19:00
Что такое нетривиальный делитель
Пусть — область целостности.
Всякий элемент а кольца делится на любой обратимый элемент кольца (на любой делитель единицы кольца) и на каждый ассоциированный с а элемент кольца. Такие делители называются тривиальными делителями элемента а.
ОПРЕДЕЛЕНИЕ. Собственным делителем элемента а называется любой его нетривиальный делитель, т. е. делитель, не ассоциированный с а и необратимый в кольце .
ОПРЕДЕЛЕНИЕ. Элемент области целостности называется составным или приводимым в , если он отличен от нуля и его можно представить в виде произведения двух необратимых элементов кольца .
Другими словами, элемент области целостности называется составным, если он отличен от нуля и его можно представить в виде произведения двух собственных делителей.
ОПРЕДЕЛЕНИЕ. Элемент области целостности называется простым или неприводимым в , если он отличен от нуля, необратим и имеет только тривиальные делители.
Отметим, что в любом поле нет простых и нет составных элементов.
Примеры. 1. В кольце целых чисел элемент , отличный от 0 и ± 1, является простым в том и только в том случае, когда его делителями являются только элементы . Простыми в кольце являются числа
2. В кольце элемент 6 составной, так как и 2, 3 — необратимые элементы.
Множество всех элементов области целостности распадается на четыре класса: 1) множество, содержащее один элемент — нуль; 2) множество всех обратимых элементов (множество всех делителей единицы); 3) множество всех простых элементов; 4) множество всех составных элементов. Последние два класса могут быть пустыми (если область целостности — поле).
ТЕОРЕМА 3.8. Пусть — область целостности, а, и 1— единица кольца . Тогда:
(5) тогда и только тогда, когда и а не делит b.
Доказательство. (1) Пусть , т. е. существует такой элемент с из К, что тогда
и, значит, Допустим теперь, что (а) с тогда и, значит, а для некоторого с из К, т. е.
(2) если а , то в силу (1). Кроме того, поскольку следовательно, Если то а в силу (1);