Проблема Ферма для простых показателей больше 3
Модуль K
Дальнейшие рассуждения требуют расширенного представления о модуле K.
Ниже покажем:
---- что для 1-го случая ПФ модуль K =eP2;
---- что для 2-го случая ПФ модуль K >3; ----- что для 2-го случая ПФ имеет место (K,P) = 1;
---- что простые числа вида 6n + 5, не могут быть делителями K (см. в разделе 1.7.);
--- что числа 3t, где t > 1, не могут быть делителями K (см.в разделе1.7.).
а) Для доказательства того, что K = eP2 для 1-го случая ПФ,
из равенств (1.38), (1.39) и (1.40) находим, что
(X + Y)P –1 є a0P mod P,
(Z – X)P –1 є a1P mod P,
(Z – Y)P –1 є a0P mod P, тогда благодаря Малой теореме Ферма имеем
a0P є 1 mod P, Ю a0P є 1 mod P2, Ю a0 = e0P + 1,
a1P є 1 mod P, Ю a1P є 1 mod P2, Юa1 = e1P + 1,
a2P є 1 mod P, Ю a2P є 1 mod P2, Юa2 = e2P + 1.
Очевидно, что XP + YP – ZP є 0 mod P2
Тогда, с учетом последних сравнений и равенств (1.15), (.18) и (1.21) имеем
a2Рd2P + a1PdP - a0Pd0P є .d0P – d2P –d1P є 0 mod P2. (1.46)
Но левая часть последнего сравнения с учетом (1.14), (1.17) и (1.20), а также равенства (1.26) будет
d0P – d2P –d1P = (X + Y) – (Z – Y) – (Z – X) = 2 (X + Y – Z) = 2Kd0d1d2 є 0 mod P2 Ю
Ю K = eP2, что и т.д. (1.47)
в) Модуль K > 3.
Это условие докажем для двух вариантов 2-го случая, а именно:
---для варианта1, когда (Z,P) =P, а (X,P) = 1 и (Y,P) =1;
---для варианта 2, когда (Z,P) = 1, а (X,P) = P и (Y,P) = 1.
Вариант, когда (Z,P) =1, (X,P) =1 и (Y,P) = P рассматривать не будем ввиду его полной аналогии с вариантом 2.
Доказательство того, что K >3 для варианта 1.
Пусть для определенности (для вариантов 1 и 2)
Z > X > Y (1.48)
Из неравенств P(X + Y) .> Z – Y > Z – X, и с учетом (1.36) имеем
d0P > d2P >d1P, отсюда d0 > d2 > d1.
Составим алгебраическую сумму (X + Y) – (Z – Y) – (Z – X) = 2(X + Y – Z и умножим правую и левую части полученного равенства на P получим P(X + Y) – P(Z – Y) – P(Z – X) = 2P(X + Y – Z), тогда благодаря равенствам (1.36) и (1.26) имеем d0P - Pd2P - Pd1P = 2PKd0d1d2 Ю d0P = Pd2P + Pd1P + 2PKd0d1d2. Разделим левую часть и последнее слагаемое правой части полученного равенства на d0 получим очевидное неравенство d0P-1 < Pd2P + Pd1P + 2PKd1d2. (в1)
Выразим d0 через числа d1 и d2 для чего из равенства (1.28) вычтем равенство (1.29) и учитывая равенства (1.31) и (1.32) получим a1 - a2 + d2P-1 - d1P-1 = a1 - a2 + (d2 - d1)(d2 + d1)q = Kd0 (d2 - d1), (в2) где q = .d2P-3 + d2P-5d12 + …..+ d22d1P-4 + d1P-3. Обозначим q (для P =5) как qmin = d22 + d12. Из (1.34), (1.35) с учетом условия (1.48) имеем a1 - a2 > 0. В п.1.4.4.(а) найдено, что a1 = e1P +1 и a2 = e2P + 1, тогда a1 - a2 = P(e1 - e2).
Пусть K = 3, тогда из равенства (в2) имеем d0 = (a1 - a2)/3( d2 - d1) + (d2 + d1)q/3 = P(e1 - e2)/3( d2 - d1) + (d2 + d1)q/3
Будем минимизировать d0, приняв d2 + d1 = 3, q = qmin и (e1 - e2) =3( d2 - d1) и, учитывая, что (d2 - d1, P) = 1** получим d0 = P + qmin = P + (d22 + d12). (в3) [** Если(d2 - d1, P) = P, то (X – Y, P) =P, но из (1.36) следует, что (X + Y,P) = P, тогда после сложения X – Y и X + Y получим (2X,P) = P, что противоречит варианту 1.]
Неравенство (в1) с учетом (в3) будет
[P + (d22 + d12)]P-1 < Pd2P + Pd1P + 2P3d1d2 Ю (в4) ЮPP-1 + (P –1)PP-2(d22 + d12) + ….+ (d22 + d12)P-1< Pd2P + Pd1P + 2P3d1d2. Далее при доказательстве будем минимизировать [P + (d22 + d12)]P-1 отбрасывая часть членов разложения.
Покажем, что 3-и члена разложения бинома (d22 + d12)P-1 >Pd2P + Pd1P. Так (d22 + d12)P-1 = (d22)P- 1 + (P – 1) (d22)P- 2d12 + …..+ (d12)P - 1 >Pd2P + Pd1P.
Одно слагаемое левой части разложения (d22)P- 1 = d2Pd2P – 2 > Pd2P Ю d2P – 2> P, это неравенство справедливо для d2 і 2 (d2 не может равняться 1, так как d2 >d1). Пусть d2 =2, тогда 2P – 2 = (1 + 1)P –2 = 1 + P – 2 + (P – 2)(P –3)/2 + ……+ P – 2 + 1 = = P + (P – 2)(P – 3)/2 + ……+ P – 2 > P Ю (P – 2)(P – 3)/2 + ……+ P – 2 > 0, что и подтверждает наше утверждение.
Предпоследние два слагаемых разложения бинома (d22 + d12)P-1 а именно: (P – 1) (d22)P- 2d12 + (d12)P –1 > Pd1P.
Для d1 і 2 имеем (d12)P- 1= d1Pd1P – 2> Pd1PЮ d1P – 2 > P, . доказательство аналогичное вышеприведенному для (d22)P- 1.
Для d1 =1 имеем (P – 1) (d22)P- 2d12 + (d12)P –1 = (P – 1) (d22)P- 2 + 1 > P, это неравенство справедливо, т.к. доказано, что (d22)P- 2 > P .
Таким образом, мы показали, что
(d22 + d12)P-1 > Pd2P + Pd1P.
Теперь покажем, что второе слагаемое разложения [P + (d22 + d12)]P-1, а именно (P –1)PP-2(d22 + d12) > 2P3d1d2 =6Pd1d2
Сократим правую и левую части неравенства на P и, принимая во внимание, что d22 +d12 > d1d2, так как d2 > d1 получим (P – 1)PP – 3 > 6, полученное неравенство справедливо для любых P > 3.
Нами показано, что несмотря на минимизацию d0 и d0P – 1, которая должна усиливать неравенство (в4), получили обратный результат
d0P-1 > Pd2P + Pd1P + 2P3d1d. (в5)
Пришли к противоречию с одной стороны
d0P-1 < Pd2P + Pd1P + 2P3d1d., а с другой стороны d0P-1 > Pd2P + Pd1P + 2P3d1d. (в.5)
Вывод: так как число K нечетное и не равно 3(тем более 1), то K >3, что и требовалось доказать для варианта 1.
.(г). Доказательство того, что K> 3 для вариант 2, когда
(X,P) = P, (Z,P) =1 и (Y,P) = 1.
(г.1) Выпишем часть формул Абеля для этого варианта.
X + Y = d0P = C0d0,
C0 = d0P –1,
Z – X = d1P = C1d1,
C1 = d1P –1,
Z – Y = d2P/P = C2d2,
C2 = d2P –1/P.
Найдем иные соотношения, которые будем использовать в дальнейших рассуждениях
Из равенства 2 (X + Y – Z) = (X + Y) – (Z – Y) – (Z – X) = 2Kd0d1d2 [с учетом (г.1)] получим
d0P – d2P/P – d1P = 2 Kd0d1d2, отсюда
d0P – d1P є 0 mod P, а значит и d0P – d1P є 0 mod P2 и d0 – d1 є 0 mod P, где d0 > P.
Пусть K =3.
Чтобы получить противоречие (для K =3) сложим равенства (1.27) и (1.28) и с учетом (г.1) имеем
d0P- 1 – d1P –1 + a2 - a0 = 3d3(d0 + d1) Ю Ю 3d3 = (d0 – d1)(d0P –3 + d0P -5d12 + …+ d02 d1P – 5 + d1P –3) + + (a2 - a0)/(d0 + d1). Это равенство не справедливо. Минимизируем правую часть полученного равенства, для чего принимаем d0 – d1 =P, отбросим слагаемое (a2 - a0)/(d0 + d1), а также принимаем P = 5, тогда 3d3 > P(d02 + d12), но и это неравенство несправедливо, так как P > 3, а d02 > d3, что следует из неравенства P(X + Y) > P(Z – Y), которое с учетом (г.1) будет Pd0P > d3P, но d02P > Pd0P , тогда d02P > d3P, отсюда после извлечения корня P-степени из правой и левой части неравенства получим d02 > d3, что и требовалось доказать.
Таким образом мы пришли к противоречию с одной стороны 3d3 > P(d02 + d12), с другой стороны
3d3 < P(d02 + d12).
Вывод: так как число K нечетное и не равно 3(тем более 1), то K >3, что и требовалось доказать для варианта 2, а по аналогии и для варианта, когда (Y,P)=P, (X,P) =1 и (Z,P) =1.
б) (K,P) = 1 для 2- го случая ПФ
Для второго случая только одно из чисел X, Y, Z кратно Р, а значит, только одно из чисел С0, С1 и С2 кратно Р (см., как пример, (1.36)). Пусть для определенности (С1,P) = P, тогда левая часть равенств (1.28), не будет делиться на Р, так как (a1,C1) =1 , а значит, и правая часть этого равенства, содержащая множителем число K, не будет делиться на Р, а это значит, что для второго случая ПФ
(K, Р) = 1. (1.49)
1.5 Вспомогательные числа и вспомогательные сравнения
Пусть {1, 2, …, ri, …, mi, ..., li, …, K – 1} – приведенная система наименьших, натуральных вычетов по модулю K. Тогда, очевидно, существуют такие числа r1, r2, r3, m1, m2, m3 и l1, l2 и l3, принадлежащие этой системе, что
r1Z – X є 0 mod K или r1Z є X mod K, (1.50)
Z – r2Y є 0 mod K или r2Y є Z mod K, (1.51)
r3X + Y є 0 mod K или r3X є –Y mod K, (1.52)
Z – m1X є 0 mod K, (1.53)
m2Z – Y є 0 mod K, (1.54)
X + m3Y є 0 mod K, (1.55)
Z 2 – l1XY є 0 mod K, (1.56)
Y 2 + l2ZX є 0 mod K, (1.57)
X 2 + l3ZY є 0 mod K. (1.58)
Умножая сравнения (1.50)–(1.52), получим
r1r2r3ZXYє – ZXY mod K,
отсюда
r1r2r3 є –1 mod K. (1.59)
Cложим сравнение (1.50) и (1.51) и, учитывая (1.26), получим
r1Z – X + Z – r2Y є r1Z + (Z – X) – r2Y є r1Z + Y – r2Y є
є r1Z – Y(r2 – 1) є 0 mod K,
а учитывая, что Z є r2Y mod K (cм. (1.51)), получим
r1r2Y – Y(r2 – 1) є 0 mod K,
отсюда
r1r2 – r2 + 1 є 0mod K Ю r1r2 є r2 – 1mod K. (1.60)
Умножая сравнение (1.60) на r3 и учитывая (1.59), получим
r2r3 – r3 + 1 є 0 mod K Ю r2r3 є r3 – 1 mod K. (1.61)
Умножая (1.61) на r1 и учитывая (1.59), получим
r1r3 – r1 + 1 є 0 mod K Ю r1r3 є r1 – 1 modK. (1.62)
Из сравнений (1.50) и (1.53) получим
r1m1 є1 modK, (1.63)
а из сравнений (1.51), (1.54) и (1.52),(1.55) получим соответственно
r2m2 є 1 mod K, (1.64)
r3m3 є 1mod K. (1.65)
Сложим сравнения (1.50) и (1.55) и, учитывая (1.51) и (1.60), получим
r1Z – X + X + m3Y є r1r2Y + m3Y є Y (r2 – 1 + m3) є 0 mod K Ю
Ю m3 є 1 – r2 modK. (1.66)
Cложим сравнения (1.52) и (1.54) и, учитывая (1.50) и (1.62), получим
m2Z – Y + r3X + Yє m2Z + r3r1Z є Z(m2 + r3r1) єє Z(m2 +r1 – 1) є 0 mod K, Ю m2 є 1 – r1 modK. (1.67)
Из сравнения (1.51) вычтем сравнение (1.53) и, учитывая (1.52) и (1.61), получим
Z – r2Y – Z + m1X є m1X – r2(–r3X) є X(m1 + r2r3) є
є X(m1 + r3 – 1) є 0 mod K Ю m1 є 1 – r3 mod K. (1.68)
Решая совместно сравнения (1.56) и (1.50) и принимая во внимание сравнение (1.51), получим
Z 2 – l1XY є Z 2 – l1r1ZY є Z(Z – l1r1Y) є Z(r2Y – l1r1Y) є
є ZY(r2 – l1r1) є 0 mod K Ю l1r1 є r2 mod K. (1.69)
Решая совместно сравнения (1.57) и (1.51) и принимая во внимание (1.52), получим
Y 2 + l2ZX є Y 2 + l2r2YX є Y(Y + l2r2X) є Y(–r3X + l2r2X) є XY(l2r2 – r3) є 0 mod K Ю l2r2 є r3 mod K. (1.70)
Решая совместно сравнения (1.58) и (1.52) и принимая во внимание (1.50), получим
X 2 + l3ZY є X2 + l3Z(–r3X) є X(X – l3r3Z) є X(r1Z – l3r3Z) є ZX(r1 – l3r3) є 0 mod K, Ю l3r3 є r1 mod K. (1.71)
Из сравнения (1.69) вычтем сравнение (1.63) и, принимая во внимание (1.60), получим
l1r1 – m1r1 є r2 – 1 є r1r2 mod K,
отсюда, сокращая на r1, получим l1 – m1 є r2 mod K, а с учетом (1.68) имеем
l1 є r2 + m1 є r2 + 1 – r3 mod K,
отсюда, так как l1, r2 и r3 меньше K, получим
l1 = r2 – r3 + 1. (1.72)
Из сравнения (1.70) вычтем сравнение (1.64) и, принимая во внимание (1.61), получим
l2r2 – m2r2 є r3 – 1 є r2r3 mod K,
отсюда, сокращая на r2, получим l2 – m2 є r3 mod K, а с учетом (1.67) имеем
l2 є r3 + m2 є r3 + 1 – r1 mod K,
отсюда, так как l2, r3 и r1 меньше K, получим
l2 = r3 – r1 + 1. (1.73)
Из сравнения (1.71) вычтем сравнение (1.65) и, принимая во внимание (1.62), получим
l3r3 – m3r3 є r1 – 1 є r1r3 mod K,
отсюда, сокращая на r3, получим l3 – m3 є r1 mod K, а с учетом (1.66) имеем
l3 є r1 + m3 є r1 + 1 – r2 mod K,
отсюда, так как l3, r1 и r2 меньше K, имеем
l3 = r1 – r2 + 1. (1.74)
1.5.6. Проведем анализ равенств, полученных в п. 1.5.5.
Из равенства (1.72) следует, что
а) r2 і r3,
тогда сложим равенства (1.73) и (1.74):
l2 +l3 = r3 – r1 + 1 + r1 – r2 + 1 = r3 – r2 + 2,
отсюда, так как числа l2 и l3 натуральные, следует, что
б) r3 і r2.
отношения а) и б) возможны только при условии, что
r2 = r3. (1.75)
Из равенства (1.73) следует, что
в) r3 і r1,
тогда сложим равенства (1.72) и (1.74):
l1 + l3 = r2 – r3 + 1 + r1 – r2 + 1 = r1 – r3 + 2,
отсюда, так как числа l1 и l3 натуральные, следует, что
г) r1 і r3,
отношения в) и г) возможны только при условии, что
r1 = r3. (1.76)
Благодаря равенствам (1.75) и (1.76) имеем равенство чисел r1, r2 и r3, тогда
r1 = r2 = r3 = r. (1.77)
Из равенств (1.72)–(1.74) с учетом равенств (1.77) следует, что
l1 = 1, l2 = 1 и l3 = 1. (1.78)
Благодаря (1.77) сравнения (1.60)–(1.62) примут вид
r2 – r + 1 є 0 modK, (1.79)
а сравнение (1.59) будет выглядеть следующим образом:
r3 є –1 modK. (1.80)
Благодаря (1.78) сравнения (1.56)–(1.58) примут вид
Z 2 – XY є 0 mod K,
Y 2 + ZX є 0 mod K,
X 2 + ZY є 0 mod K,
а с учетом (1.26) –
(X + Y)2 – XYє 0 modK, (1.81)
(Z – X)2 + ZXє 0 modK, (1.82)
(Z – Y)2 + ZYє 0 modK. (1.83)
1.6 Противоречия сравнений и равенств
Противоречие 1
Все сравнения по модулю K, в том числе и (1.79) и (1.80), будут справедливы для любого простого делителя, принадлежащего числу K. Для первого случая ПФ благодаря (1.49) таким простым делителем, принадлежащим K, будет число Р, тогда сравнения (1.79) и (1.80) по модулю Р будут соответственно
r2 – r + 1 є 0 mod P, (1.84)
r3 є –1 mod P. (1.85)
Благодаря Малой теореме Ферма имеем
r P–1 – 1 є 0 mod P. (1.86)
Пусть Р = 6n + 5, тогда сравнение (1.86) с учетом сравнения (1.85) будет выглядеть следующим образом:
r 6n + 5 – 1 – 1 = r 6n+ 4 – 1 = (r3)2n + 1r – 1 є (–1)2n + 1r – 1 є 0 mod P,
отсюда r є – 1 mod P, тогда с учетом этого сравнения (1.50) и (1.51) будет иметь вид (–1)Z є X mod P , Z є (–1)Y є 0 mod P. Тогда после вычитания сравнений получим
- 2Z є X + Y mod P Ю с учетом (1.26) 3Z є 0 mod P, что невозможно, так как (Z,K) =1 и Р = 6n + 5 > 3. Пришли к противоречию .
Первый случай ПФ для простых показателей вида 6n + 5 доказан.
Противоречие 2
Сравним равенства (1.44) и (1.45) по модулю K 2 с учетом сравнения (1.81). для P вида 6n + 1 (S = 2). Очевидно, что левые части равенств (1.44) и (1.45) сравнимы с нулем по модулю K 2, т.е.
РXY
[(X
+ Y)2 – XY]2
є 0
mod K 2,
XY [(X
+ Y)2 – XY]2
є 0
mod K 2,
тогда и правые
части равенств
(1.44) и (1.45) должны быть
сравнимы с
нулем по модулю
K 2, т.е.
є 0 mod
K2.
Разложим левую часть полученного сравнения, воспользовавшись теоремой 1.1, получим
–
=
(С0 – a0)P
+ PC0a0(C0
– a0)P–2
+ … AP–3/2
(C0 – a0)3
+
(C0 – a0)
є
0 mod K2.
Из (1.27) следует,
что С0 – a0
є 0 mod
K, учитывая
это, отбросим
все слагаемые
полученного
разложения,
содержащие
множитель (С0
– a0)i,
где i і
3, получим
(C0
– a0)
є 0
mod K 2,
отсюда с
учетом (1.27)
d1d2
є 0
mod K, что
невозможно,
так как ни один
простой делитель
числа K,
не принадлежит
ни С0, ни a0
, ни d1.ни d2
(см. 1.3.6.). Число
Р, также не может
делиться на
K, так как
для первого
случая ПФ K
кратно Р2 [
(1.47)], а для
второго случая
(K, Р) = 1 [см.
(1.49)].
Пришли к противоречию: левые части (1.44) и (1.45) делятся на K 2, а правые их части не делятся на K 2.
Проблема
Ферма (первый
и второй случаи)
для всех простых
показателей
Р = 6n