blog.iakovlev.org
  10.01.2016

Теория сравнений

В 1849 году Чебышёв защитил в Петербургском университете докторскую диссертацию «Теория сравнений». Она стала первой отечественной монографией по теории чисел. Этот труд несколько раз переиздавался, был переведен на немецкий и итальянский языки.
Во введении Чебышёв отмечает нескольких математиков, внесших вклад в развитие теории чисел - Ферма, Эйлера, Лагранжа, Лежандра, Гаусса. Чебышёв пишет, что теория чисел есть наука о решении неопределенных уравнений в целых числах. Она отличается от арифметики тем, что рассматривает числа только в отношении их способности удовлетворять неопределенным уравнениям. Она отличается от алгебры тем, что рассматривая уравнения, она ограничивается только целыми значениями неизвестных.
Книга состоит из нескольких глав, в частности:
1. Глава первая. О сравнении вообще.
2. Глава вторая. О сравнении первой степени.
3. Глава третья. О сравнениях высших степеней вообще
...
7. Глава седьмая. О сравнениях второй степени с двумя неизвестными.
В конце книги есть приложения по простым числам, квадратичным формам.
Книга построена по принципу доказания теорем общим числом более 30. Подробные доказательства можно найти в самой книге Чебышёва Теория сравнений

Введение

Начнем с первой теоремы.
Теорема 1
Если два числа A и B взаимно просты с третьим число C, то и произведение AB будет числом, взаимно простым с C.

Теорема 2
Пусть два числа C и A взаимно просты. Пусть есть третье число B, такое, что произведение AB делится на C. Тогда B делится на C.

Теорема 3
Пусть два числа A и B взаимно просты. Пусть есть третье число C, которое делится и на A, и на B. Тогда C делится и на произведение AB.

Далее Чебышёв переходит к рассмотрению канонического разложения числа и формулирует следующие теоремы:
Теорема 4
Число N может делиться на число P только в том случае, когда все простые множители числа P входят в состав простых множителей числа N, где степени их не ниже, чем в P.

Теорема 5
Для числа N возможно только одно разложение на простые множители.

На основе этих двух теорем о разложении доказываются следующие:

Теорема 6
Если N делит квадрат числа M, но само не может делиться на квадрат какого-нибудь числа, то N делит и само число M.
Например, пусть N=15. В его каноническом разложении все простые числа находятся в первой степени. Пусть M=45, и его квадрат равен 2025. Если 2025 кратно 15, то и 45 кратно 15.

Теорема 7
Пусть дано число N. Корень h-й степени из этого числа есть число целое только в том случае, когда степени его простых множителей кратны h.
Например, если рассмотреть число 576=2632 , видно, что только корень квадратный из 576 является целым числом.

С помощью следующей теоремы можно определить сумму делителей числа и число этих делителей:
Теорема 8
Пусть число N имеет каноническое разложение в виде N = αmβnγp....
Тогда число делителей числа N есть (m+1)(n+1)(p+1)... , а сумма различных делителей есть:

Например, число 72 = 2332, имеет сумму делителей, равную (24-1)⁄(2-1) * (33-1)⁄(3-1) = 195 , а число делителей равно (3+1)*(2+1) = 12, что соответствует действительности, поскольку делителями числа 72 являются числа 1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72

Теорема 9
Пусть число N имеет каноническое разложение в виде N = αmβnγp...,
где по крайней мере одно из чисел m, n, p ... есть число нечетное.
Тогда число N можно разожить на два множителя числом способов, равных 0.5(m+1)(n+1)(p+1)...,
Если же все показатели четные, то число таких разложений равно 0.5(m+1)(n+1)(p+1)... + 0.5,
Например, число 72 = 2332, число разложений равно 0.5(3+1)(2+1)=6:
1*72, 2*36, 3*24, 4*18, 6*12, 8*9
Для числа 36 = 2232, число разложений равно 0.5(2+1)(2+1) = 5:
1*36, 2*18, 3*12, 4*9, 6*6

Следующая теорема сформулирована для арифметических прогрессий:
Теорема 10
Если разность прогрессии есть число, взаимно простое с p, а число членов равно mp, то в такой прогрессии число членов, делящихся на p, равно m,

Теорема 11
Пусть a - простое число. Пусть b - число, взаимно простое с a.
Рассмотрим ряд 1, 2, 3, ..., abN-1.
Тогда число членов этого ряда, взаимно простых с b, относится к числу членов этого ряда, взаимно простых с a и b, как a к a-1,

На основании этих двух теорем можно вывести следующую, которая является аналогом известной теоремы Эйлера о числе взаимно простых:
Теорема 12
Пусть число N имеет каноническое разложение в виде N = αmβnγp...πr,
тогда число чисел, взаимно простых с N и меньших N, равно

Например, 36 = 2232. Число чисел, взаимно простых с 36 и меньших, чем 36, равно 2232 * ((2-1)⁄2)((3-1)⁄3)=12.

Глава 1 О сравнении вообще

Теория сравнений имеет предметом исследования неопределенные уравнения, в которых одна из неизвестных входит в первой степени. Общий вид таких уравнений:
F(x,y,z...) = Au + B
где F - данная функция, A и B - известные числа. Если число u неизвестно, то

Последнее уравнение можно представить в виде
F(x,y,z...) ≡ B(мод A)
Например, для записи: 17-5 делится на 3:
17 ≡ 5(мод 3)
Вообще, выражение вида
M ≡ N(мод A)
читается как сравнение, числа M и N называются сравнимыми по модулю A, число A - модуль сравнения. M и N могут быть как числами положительными, так и отрицательными, A всегда положительно.
Если через r обозначить остаток от деления M на A, q - частное при деления M на A, то
M = Aq + r
Если M делится на A без остатка, то
M ≡ 0(мод A)
Сравнения имеют свойства:
1. Два числа, сравнимые с каким-то числом по одному модулю, сравнимы и между собой по тому же модулю.
2. В сравнениях, подобно уравнениям, члены могут быть переносимы из одной части в другую.
3. Два или несколько сравнений с одним и тем же модулем можно почленно складывать и вычитать.
4. Члены сравнения могут быть умножены на одно и то же число.
5. Два или несколько сравнений с одним и тем же модулем можно почленно перемножить.
6. Значения целой функции с целыми коэффициентами от двух чисел, сравнимых по какому-нибудь модулю, сравнимы по тому же модулю.
7. Члены сравнения могут быть сокращены на их общего множителя, если этот множитель - взаимно простое с модулем.
8. Если одна часть сравнения и модуль делятся на какое-нибудь число, то на то же число должна делиться и другая часть сравнения.
9. Общий множитель членов сравнения и модуля может быть сокращен.
10. Два числа, сравнимых по двум или нескольким модулям, которые взаимно просты. сравнимы и по их произведению.
11. Не нарушая сравнения, модуль может быть заменен числом, на которое он делится.

Следуюшая теорема для сравнения с одним неизвестным, где f(x) - целая функция с целыми коэффициентами.
Теорема 13
Если сравнению f(x) ≡ 0(мод p) эквивалентно равенству x = a, то оно равно для всех чисел, сравнимых с a по модулю p.
Из всех таких чисел, сравнимых с a по модулю p, особого внимания заслуживают два:
1. Наименьшее положительное из всех чисел, сравнимых с a по модулю p - наименьший положительный вычет из a по модулю p,
1. Наименьшее по модулю отрицательное из всех чисел, сравнимых с a по модулю p - наименьший отрицательный вычет из a по модулю p,
Одно из двух этих чисел, наименьшее по модулю, называтеся абсолютно малым вычетом из a по модулю p,
Например, для определения наименьшего положительного вычета числа 23 на число 7 в формуле 23 -7N, где N=3, и вычет равен 2.
Для определения наименьшего отрицательного вычета числа 23 на число 7 в формуле 23 -7N N = 23/7 = 3 + 2/7. Вместо 2/7 подставляем 1 , получаем N=4, отсюда наименьший отрицательный вычет равен 23 -7*4 = -5.

Глава 2 О сравнении первой степени

Общий вид сравнений первой степени такой:
ax - b ≡ 0(мод p)
где a, b - какие-нибудь числа, положительные или отрицательные, и p - число положительное.
Здесь возможны два случа1: первый - числа a и p - взаимно простые, второй - имеют общий множитель. Для первого случая справедлива следующая теорема:
Теорема 15
Сравнение ax - b ≡ 0(мод p) при a взаимно простом с p всегда имеет одно решение.

Далее следуют две теоремы - малая теорема Ферма и теорема Эйлера, которая является обобщением малой теоремы Ферма. Малая теорема Ферма впервые была доказана также Эйлером.
Теорема 16
Если p - число простое и не делит a, то ap-1 ≡ 1(мод p)
Доказательство:
Возьмем в качестве примера a=12 и p=7.
Посчитаем вычеты для a, 2a, 3a, ... , (p-1)a:
12 ≡ 5(мод 7)
24 ≡ 3(мод 7)
36 ≡ 1(мод 7)
48 ≡ 6(мод 7)
60 ≡ 4(мод 7)
72 ≡ 2(мод 7)
Видно, что ряд вычетов состоит из 1, 2, 3, ... , p-1
Перемножим эти шесть сравнений друг на друга и получим:
1*2*3*4*5*6*a6=1*2*3*4*5*6 (мод 7)
Поскольку левую и правую часть сравнения можно сокращать так же, как и обычное уравнение, после сокращения получаем:
a6=1 (мод 7)
что и требовалось доказать.

Следующая теорема называется теоремой Эйлера и является обобщением для предыдущей теоремы.
Теорема 17
Пусть дано число m. Пусть в интервале от 1 до m, не включая m, находятся числа, взаимно простые с m. Число этих взаимно простых чисел обозначим как n. Пусть есть третье число a, которое является взаимно простым с m. Тогда
an ≡ 1 (мод m)
Доказательство:
Пусть m = 12. Для этого числа будет четыре числа, взаимно простых с m и меньших m: 1, 5, 7, 11. Т.е. n = 4. И возьмем какое-нибудь произвольное a, взаимно простое с m, например a = 17. Тогда
174 ≡ 1 (мод 12)
Для доказательства вычислим сравнения для каждого из этих 4-х взаимно простых чисел, при этом каждое число умножим на a, по модулю m:
17*1 ≡ 5 (мод 12)
17*5 ≡ 1 (мод 12)
17*7 ≡ 11 (мод 12)
17*11 ≡ 7 (мод 12)
После чего перемножим эти сравнения:
1*5*7*11*174 ≡ 1*5*7*11 (мод 12)
Разделив обе части на 1*5*7*11, получаем
174 ≡ 1 (мод 12)
что и требовалось доказать

На основании последних двух теорем можно решать сравнения вида
ax - b ≡ 0 (мод p)
Эти сравнения можно разделить на две категории: первая - когда p взаимно простое с a и само p простое, и вторая - когда p взаимно простое с a, но само p - составное.
В первом случае x можно найти по формуле
x ≡ bap-2 (мод p)
Например: 3x - 8 ≡ 0 (мод 5)
3x - 8 ≡ 0 (мод 5)
x ≡ 8*35-2 (мод p)
x ≡ 216 (мод p)
x ≡ 1 (мод p)

Во втором случае x можно найти по формуле
x ≡ ban-1 (мод p)
Во втором случае нужно дополнительно находить число n, которое есть число чисел, взаимно простых с p и меньших p. Его можно найти по формуле из теоремы 12.
Например: 3x - 8 ≡ 0 (мод 5)
2x - 7 ≡ 0 (мод 15) , где 15=3*5
x ≡ 7*27 (мод 15)
x ≡ 896 (мод 15)
x ≡ 11 (мод 15)

Сравнение первой степени
ax ≡ b (мод p)
не имеет решения, если a и p имеют общий множитель, который не делит b.
Теорема 18
Сравнение ax - b ≡ 0 (мод p) не имеет решения, если общие множители a и p не делят b.

Теорема 19
Если a и p имеют наибольший общий делитель (НОД) d, и d делит b, то сравнение ax - b ≡ 0 (мод p) имеет d решений, которые могут быть представлены как:
x ≡ α (мод p)
x ≡ α + p/d (мод p)
x ≡ α + 2p/d (мод p)
...
x ≡ α + (d-1)*p/d (мод p)
где α есть число, меньшее чем p/d b и большее 0, найдено может быть из сравнения:
(a/d)*x - b/d ≡ 0 (мод p/d)

Например, рассмотрим сравнение 15x - 9 ≡ 0 (мод 12)
Здесь 15 и 12 имеют общий делитель 3, b также делится на 3, сравнение имеет три решения. Сначала нужно найти α. Перепишем сравнение, сократив его на d=3:
5x - 3 ≡ 0 (мод 4)
Это сравнение относится к случаю, когда p взаимно простое с a, но само p - составное. Решение можно найти по формуле (см. выше):
x ≡ ban-1 (мод p)
x ≡ 3*5 (мод 4)
x ≡ 3 (мод 4)
Т.о. мы нашли число α=3. Далее находим три решения исходного сравнения по модулю 12 по теореме 19:
x≡3 x≡3+4 x≡3+8 (мод 12)
x≡3 x≡7 x≡11 (мод 12)

Глава 3 О сравениях высших степеней

В этой главе будут рассмотрены сравнения с простыми модулями. Общий вид таких сравнений будет иметь вид:
Axm + Bxm-1 + Cxm-2 + ... + Hx + S ≡ 0 (мод p)
где p - простое число, A, B, C, ... , H, S - какие-то числа.
Если предположить, что все коэффициенты, кроме A, кратны модулю p, то сравнение может быть приведено к виду
Aα - 1 ≡ 0 (мод p)
где α - это альфа. Последнее сравнение можно в свою очередь привести к виду
xm + Bαxm-1 + Cαxm-2 + ... + Hαx + Sα ≡ 0 (мод p)
Рассмотрим пример: нужно решить сравнение
2x3 + 3x + 7 ≡ 0 (мод 11)
Сначала нужно найти альфа:
2α - 1 ≡ 0 (мод 11)
Здесь α = 6. Умножаем последнее сравнения сначала на 3x, потом на 7:
2*3*6*x - 3*x ≡ 0 (мод 11)
2*7*6 - 7 ≡ 0 (мод 11)
Складываем эти сравнения с исходным и получаем
2x3 +2*3*6*x + 2*6*7 ≡ 0 (мод 11)
Сокращаем на 2 и получаем коэффициент при высшей степени 1
x3 +18x + 42 ≡ 0 (мод 11)

Далее идут несколько теорем
Теорема 20
При p простом сравнение xm + Bxm-1 + Cxm-2 + ... + Hx + S ≡ 0 (мод p) не может иметь более m решений.

Теорема 21
Если в сравнении xm + Bxm-1 + Cxm-2 + ... + Hx + S ≡ 0 (мод p) не все коэффициенты делятся на p, то оно более m решений иметь не может.

Теорема 22
Коэффициенты всех степеней x в разложении уравнения
(x-1)(x-2)(x-3)...(x-p+1) - xp-1 + 1
делятся на p, если p число простое
В частности,
(-1)p-1*1*2*3*...*(p-1) + 1 ≡ 0 (мод p)
Последнее сравнение приводит к теореме Вильсона

Теорема 23
Если p число простое, то
1*2*3*...*(p-1) + 1 ≡ 0 (мод p)

Теорема 24
Если p число простое, то сравнение
xm + Bxm-1 + Cxm-2 + ... + Lx + M ≡ 0 (мод p)
может быть заменено сравнением степени p-1
A1xp-1 + B1p-2 + C1xp-3 + ... + L1x + M1 ≡ 0 (мод p)
Последний полином есть остаток от деления исходного полинома на xp - x.

Например, дано сравнение
x5 + x2 - 1 ≡ 0 (мод 3)
Его степень можно понизить до 2, разделив его на x3 - x
x2 + x - 1 ≡ 0 (мод 3)

Теорема 25
Если сравнение
xm + Bxm-1 + Cxm-2 + ... + Lx + M ≡ 0 (мод p)
имеет m решений, то в остатке от деления xp - x на xm + Bxm-1 + Cxm-2 + ... + Lx + M все коэффициенты делятся на p.

Теорема 26
Если остаток от деления xp - x на xm + Bxm-1 + Cxm-2 + ... + Lx + M имеет все коэффициенты, кратные p, то сравнение xm + Bxm-1 + Cxm-2 + ... + Lx + M ≡ 0 (мод p) имеет m решений.

На основании последних двух теорем всегда можно узнать, имеет ли данное сравнение столько решений, сколько в показателе его степеней содержится единиц. Для этого коэффициент при высшей степени нужно сделать равным единице, далее делим xp - x на полученное сравнение. Если остаток имеет все коэффициенты, кратные p, то данное сравнение имеет столько решений, сколько в показателе его степени имеется единиц. Иначе оно имеет меньше решений.
Например, в сравнении
x3 + x2 + 2x ≡ 0 (мод 5)
мы хотим узнать, имеет ли оно три решения. Делим
x5 - x на
x3 + x2 + 2x
Остаток от деления есть
5x2 + 5x
оба коэффициента в котором делятся на 5, значит оно имеет 3 решения.

...


Глава 7 О сравнениях второй степени с двумя неизвестными

В этой главе мы рассмотрим сравнения вида
x2 + Ay2 + B ≡ 0 (мод p)
Пусть p - число простое, отличное от 2, и q - число, не делящееся на p. пусть имеется сравнение z2 ≡ q (мод p). Оно может иметь решение в завивсимости от того, какое решение имеет другое сравнение:

Если последнее сравнение равно +1, то сравнение z2 ≡ q (мод p) имеет решение, при этом q называется квадратичным вычетом числа p, в противном случае сравнение z2 ≡ q (мод p) не имеет решения, при этом q называется неквадратичным вычетом числа p,
Вместо

пишут для краткости

или (q/p)=1

Теорема 50
Если p число простое и не делит A, то сравнение x2 + Ay2 + B ≡ 0 (мод p) всегда имеет решение
Из данной теоремы в частности вытекает, что сравнение x2 + y2 + 1 ≡ 0 (мод p) имеет решение

Рассмотрим исходное сравнение при B=0
x2 + Ay2 ≡ 0 (мод p)
Найдем, какие свойства имеет в нем число p при условии, что x и y взаимно просты. При этом число p может быть делителем квадратичной формы x2 + Ay2. Мы найдем фомулы, по которым можно найти эти делители, которые будут представлены в виде mz + a, где z - произвольное число - это составляет теорию линейных делителей квадратичных форм. Также эти формулы делителей могут быть выражены в виде au2 + 2buv + cv2, где u и v - взаимно простые числа, и это входит в теорию квадратичных делителей квадратичных форм.

Следующая теорема лежит в основании теории линейных делителей:
Теорема 51
Если сравнению x2 + Ay2 ≡ 0 (мод p) удовлетворяют какие-нибудь взаимно простые числа x, y, то сравнение u2 + A ≡ 0 (мод p) имеет решение.

Теорема 52
Если A - простое число вида 4n + 3 и p нечетный делитель формы x2 + Ay2, то (p/A)=1

Теорема 53
Если A простое число вида 4n+1 и p делит x2 + Ay2, то (p/A) = (-1)(p-1)/2, т.е. (p/A)=1, если p=4m+1, и (p/A)=-1, если p=4m+3.

Теорема 54
Если A простое число вида 4n+1 и p нечетный делитель формы x2 - Ay2, то (p/A)=1

Теорема 55
Если A простое число вида 4n+3 и p нечетный делитель формы x2 - Ay2, то (p/A)=(-1)(n-1)/2, т.е. (p/A)=1, если p вида 4m+1, (p/A)=-1, если p вида 4m+3.

С помощью этих теорем можно определить все линейные делители форм вида x2 ± Ay2. Нечетные делители таких форм определяются или уравнением (p/A)=1, или уравнением (p/A)=-1. Этот знак при единице зависит от нескольких факторов:
1. какой знак стоит в форме x2 ± Ay2
2. какого вида A - либо 4n+3, либо 4n+1
3. иногда - от того, какого вида p - 4m+3, либо 4m+1
стр.130
Рассмотрим пример: возьмем форму x2 - 7y2 и найдем ее делители.
Число 7 имеет вид 4n+3, поэтому по теореме 55 делители этой формы вида 4m+1 должны удовлетворять уравнению (p/7)=1, а делители вида 4m+3 должны удовлетворять уравнению (p/7)=-1. Чтобы найти числа, удовлетворяющие (p/7)=1, мы должны рассмотреть числа в ряду 1,2,3,...,7, т.е. меньшие или равные числу (7-1)\2. Т.о. такими числами являются первые три числа - 1,2,3. Возводим каждое из этих чисел в квадрат и делим на 7, получаем 3 остатка: 1,4,2.
Таким образом, это должны быть числа вида 7n+1, 7n+4, 7n+2. Подставляем 4m+1 в 7n+1 и получаем
4*7z + 7r + 1
Здесь r - одно из чисел 0,1,2,3, которое с 7*(1-1), или 0, сравнимо по модулю 4. Это число есть 0. Остается 4*7z+1, или 28z+1.
Аналогично поступаем с формулами 7n+4, 7n+2. Из них мы выводим
4*7z+7r+4
4*7z+7r+2
где r - числа из ряда 0,1,2,3, которые с 7(1-4) и 7(1-2) сравнимы по модулю 4. Это числа 3 и 1. Имеем
4*7z+3*7+4
4*7z+3*7+4
или 28z+25 и 28я+9
Т.о. все числа вида 4m+1, удовлетворяющие уравнению (p/7)=1, и способные быть делителями формы x2-7y2, определяются формулами
28z+1, 28z+9, 28z+25
Чтобы найти делители вида 4m+3, рассмотрим уравнение (p/7)=-1. В ряду чисел 1,2,3,4,5,6 выкидываем те, которые равны остаткам от деления 12,22,32 на 7. Выкидываем 1,2,4, остаются 3,5,6. Перемножаем 7n+3, 7n+5, 7n+7 на 4m+3, получаем
4*7z+7r+3, 4*7z+7r+5, 4*7z+7r+6
Здесь r может быть числом из ряда 0,1,2,3, которые сравнимы с 7(3-3), 7(3-5), 7(3-6) по модулю 4. Находим
r=0, r=2, r=3
Подставляем
4*7z+7*0+3, 4*7z+7*2+5, 4*7z+7*3+6
Получаем
28z+3, 28z+19, 28z+27
Подведем итоги: для формы x2 - 7y2 найдены шесть формул делителей. Делители вида 4m+1 определяются формулами
28z+1, 28z+9, 18z+25
Делители вида 4m+3 определяются формулами
28z+3, 28z+19, 18z+27

Теорема 60
Всякий делитель формы x2 - dy2 может быть представлен квадратичной формой, имеющей определителем d.

Теорема 61
Делитель x2 - Dy2 при D>0 может быть представлен формою au2 + 2buv - cv2, где ac+b2=D, числа a и c положительные, не меньшие, чем 2b, и b не превосходит корня квадратного из D/5.

Теорема 62
Делитель x2 + Dy2 при D>0 может быть представлен формою au2 + 2buv + cv2, где ac-b2=D, числа a и c положительные, не меньшие, чем 2b, и b не превосходит корня квадратного из D/3.

Рассмотрим пример. Пусть дана форма
x2 + y2
По теореме 62, делители ее будут представляться формами
au2 + 2buv + cv2
причем ac - b2=1, b не превосходит корня из 1/3, что кстати говорит о том, что b=0. Уравнение ac - b2=1 при b=0 дает ac=1, откуда a=1, c=1. Из чего мы делаем вывод, что все делители формы x2 + y2 представляются формой u2 + v2

Рассмотрим другой пример. Пусть дана форма
x2 + 2y2
По теореме 62, делители ее будут представляться формами
au2 + 2buv + cv2
причем ac - b2=2, b не превосходит корня из 2/3, что кстати опять же как и в предыдущем примере говорит о том, что b=0. Уравнение ac - b2=1 при b=0 дает ac=2, откуда a=2, c=1 либо a=1, c=2 . Из чего мы делаем вывод, что все делители формы x2 + y2 представляются либо формой 2u2 + v2, либо формой u2 + 2v2, но они тождественны между собой.

Рассмотри третий более сложный пример - x2 - 21y2
По теореме 61, делители этой формы будут представлены формами
au2 + 2buv - cv2
в которых b не больше, чем корень квадратный из 21/5, ac + b2=21
Очевидно, что b может иметь только три значения - 0,1,2. Подставляя b в уравнение ac + b2=21, и учитывая, что a и c больше нуля и не менее 2b, найдем все значения, которые могут иметь a,b,c в форме au2 + 2buv - cv2, которая определят делители для x2 - 21y2.
Если b=0, то ac=21, где возможны 4 варианта:
a=1, c=21; a=7, c=3; a=3, c=7; a=21, c=1
Все эти варианты удовлетворяют условию: a>0, c>0, a>2b, c>2b,
Если b=1, то ac=20, где возможны также 4 варианта:
a=5, c=4; a=2, c=10; a=10, c=2; a=4, c=5;
Если b=2, то ac=17, и здесь нет ни одного варианта.
В результате мы имеем 8 форм:
u2 - 21v2,
3u2 - 7v2,
7u2 - 3v2,
21u2 - v2,
2u2 + 2uv - 10v2,
4u2 + 2uv - 5v2,
5u2 + 2uv - 4v2,
10u2 + 2uv - 2v2.


Глава 8 Приложение теории сравнений к разложению чисел на простые множители

При разложени больших и очень больших чисел на множители обычный алгоритм проверки предусматривает деление числа N на таблицу простых чисел, которые меньше корня из N, что становится неэффективным при возрастании N.
Мы рассмотрим другие алгоритмы и несколько частных случаев, и начнем с того, что рассмотрим числа вида am+1 и am-1

Начнем с чисел вида am - 1
Теорема 66
Если p нечетное число и делит am-1, то p может быть выражено формой wz + 1, где w - делитель m (включая сюда и 1), z - число взаимно простое с m/w, притом p должно делить aw - 1.

Теорема 67
Если 2n + 1 число простое. то простые нечетные делители a2n+1 - 1 должны быть вида 2(2n+1)z+1 или делить a-1; притом они должны быть делителями формы x2 - ay2

Рассмотрим алгоритм разложения чисел вида am - 1. Для примера возьмем число 223 - 1, оно равно 8388607. 23 - число простое, поэтому делители 223 - 1 должны иметь вид 46z+1 и быть в то же время одного из двух видов: 8m + 1 или 8m - 1(Теорема 56). При этом z может быть одного из 4 видов:
4x, 4x+1, 4x+2, 4x+3
Для этих z форма 46z+1 приводится к следующим 4:
184z+1, 184z+47, 184z+93, 184z+139
из которых последние две не дают чисел вида 8m+1 и 8m-1.
Поэтому для делителей числа 8388607 возможны только две формы:
184z+1, 184z+47
Ищем в диапазоне от 1 до корня из 8388607, подставляя в эти две формы числа от 1 до 15. Среди результатов получаем следующие простые числа:
599, 967, 1151, 1289, 1657, 2393.
Ни одно из них не делит число 8388607, из чего мы заключаем, что оно простое.
Таким же образом Эйлер нашел, что 231 - 1 = 2147483647 есть число простое
Следующий код вычисляет простые числа вида 2n - 1 в диапазоне n=31...100 и находит три простых числа:
Код

Теперь перейдем к числам вида am + 1
Теорема 70
Все нечетные делители числа 22n + 1 должны быть вида 2*2n*z + 1
Доказательство: Все нечетные делители могут быть представлены в виде 2wz+1, где w есть делитель 2n, который в частном дает число нечетное. Этому условию удовлетворяют только w=2n, поэтому все нечетные делители должны быть представлены как 2*2n*z + 1

В качестве примера возьмем два числа:
224 + 1 = 65537 и
225 + 1 = 4294967297
Делители первого числа должны быть вида 32z + 1. Берем z=1,2,3,4,5,6,7 и получаем 33,65,97,129,161,193,225. Из этих чисел только два простых числа - 97 и 193, которые не делят первое число, значит - оно простое.
Для второго числа имеем форму 64z + 1. Здесь z = 1,2,3,...,1023. Среди этих простых чисел имеется простое число 641, которое делит второе число, значит - оно составное.
Следующий код иллюстрирует данный алгоритм: он проверяет числа Ферма 22n + 1 и показывает, что начиная с n=5, идут только составные числа:
Код


Теперь переходим к числам произвольной формы. Покажем, как для любого числа может быть найдено множество форм вида x2 ± ay2 с незначительными величинами a, с помощью которых можно выражать кратные этого числа, а потом и делители.
Каким бы ни было проверяемое число, его всегда можно представить в виде A = x2 + ay2
Из найденных форм наиболее выгодны будут те, у которых a будет минимально. Такие формы могут быть найдены на основании следующей теоремы:
Теорема 71
Если d0, d1, d2, ... есть ряд чисел, в котором каждый член dn+1 по двум предыдущим определяется уравнением

если первое число в этом ряду есть единица, второе - (A - (E*√A)2), то всякая из форм x2 - Dy2, где D равно (-1)α+β+γ+...dαdβdγ... , способна выражать A или кратное A.

В качестве примера возьмем число 8520191.
На основании теоремы 71 мы будем искать делители этого числа. Для этого мы определим числа d0, d1, d2, ... по уравнениям:

Функция E - это модуль числа.
Из этиз уравнений находим:
d0=1, d1=5467, d2=370, d3=4319,
d4=1313, d5=2630, d6=3185, d7=203,
d8=1169, d9=4523, d10=242, d11=1855,
d12=593, d13=2854, d14=2965, d15=371, d16=1210.
Разложим эти числа на простые множители:
d0=1, d17*11*71, d2=2*5*37, d3=7*617,
d4=13*101, d52*5*263, d6=2*72*13, d7=7*29,
d8=7*167, d94523, d10=2*112, d11=5*7*53,
d12=593, d132*1427, d14=5*593, d15=7*53, d16=2*5*112.
Среди этих чисел можно выделить числа с индексами 6, 10, 16, как числа, в разложении которых присутствуют квадраты, которые могут быть сокращены, после чего данные числа оказываются минимальными. Между этими тремя числами также можно составить различные комбинации. Для формы делителей, имеющей вид x2 - ay2, коэффициент a может принимать следующие минимальные значения:
a = (-1)6d6 = 5*72*13
a = (-1)10d10 = 2*112
a = (-1)16d16 = 2*5*112
a = (-1)10+16d10d16 = 22*5*114
a = (-1)6+10+16d6d10d16 = 52*72*13*22*114
a = (-1)2+16d2d16 = 22*52*37*112
a = (-1)4+6+10+16d4d6d10d16 = 132*101*52*72*22*114
Исключая все множители, составляющие точные квадраты, находим для a следующие величины:
5*13, 2, 2*5, 5, 13, 37, 101
Т.о. делители числа 8520191 должны иметь вид делителей каждой из следующих форм:
x2 - 5*13y2
x2 - 2y2
x2 - 2*5y2
x2 - 5*y2
x2 - 13y2
x2 - 37y2
x2 - 101y2
Далее с помощью алгоритма линейных делителей находятся простые делители, как это делается в теореме 55, после чего с их помощью проверяем заданное число.
Следующий код иллюстрирует данный алгоритм:
Код







 Автор   Комментарий к данному блогу
Комментарий

Ваше имя:
Комментарий:
Оба поля являются обязательными