УДК 511.522.2

С. М. Вахтеров
МГТУ им. Н.Э.Баумана

г. Москва, Россия

ДОКАЗАТЕЛЬСТВО ВЕЛИКОЙ ТЕОРЕМЫ ФЕРМА

ПРИ УСЛОВИИ: НОД(φ(x), φ(y), φ(z), e) = e

В работе доказывается теорема, касающаяся Великой теоремы Ферма, для указанного в заголовке условия.

Полученный результат не завершает доказательство ВТФ, начатое в работе “Криптосистема RSA против ВТФ”[5], но приводит к результатам, которые помогают существенно ограничить область допустимых значений переменных уравнения простыми математическими операциями.

Данное доказательство ВТФ [1] для уравнения Ферма, слегка измененного вида:

 = 0,

где e - простое число больше двух, подразумевает две части (по свойствам функции Эйлера):

1)     (φ(x), φ(y), φ(z), e) = 1,

2)     (φ(x), φ(y), φ(z), e) = e.


Здесь и далее именно так (скобками) будет обозначаться наибольший общий делитель - Greatest Common Divisor.

Оба указанных случая не надо путать с известными Случаями 1 и 2 ВТФ, о которых можно почитать в [1]. Случай 1 рассматривает доказательство ВТФ, при  условии, что ни одно из значений переменных уравнения, не кратно степени e, Случай 2, подразумевает доказательство противного случая, когда только одно из значений переменных кратно e:

В данном доказательстве активно используется функция Эйлера φ(n),  где n — натуральное число, равна количеству натуральных чисел, не больших n и взаимно простых с ним, [4].  Например,  φ(9) имеет шесть таких чисел: 1, 2, 4, 5, 7 и 8 взаимно простых 9.

 ≡ 1 mod (q), для всех a взаимно простых с q.

Функция Эйлера играет ключевую роль в криптосистеме RSA.

Для случая (φ(x), φ(y), φ(z), e) = 1 доказательство выполнено на математических свойств функции Эйлера, использованных также в криптосистеме RSA в  работе [2]. С упрощенным вариантом полученного результата (для  уравнения   = 0) можно ознакомиться здесь: “Доказательство ВТФ для n=3 (для любителей)” [6].

Данное доказательство развивает идеи метода Лежандра, использованные при доказательстве теоремы Софи Жермен [1] и первоначальной версии подобного доказательства [5].

Теорема. Уравнение ++ = 0 не имеет решений, если:

1)    (φ(x), φ(y), φ(z), e) = e, т.е. все целые числа x, y, z, имеют значения функции Эйлера, кратные e. e – простое число больше 2.

2)    Выполняется хоть одно из следующих условий:
≢ 1 mod (x) и (x,e)=1;
≢ 1 mod (y) и (y,e)=1;
≢ 1 mod (z) и (z,e)=1.

Доказательство

Предположим, что условия теоремы выполнены.

Все переменные в основном уравнении ВТФ равноправны:

 ++ = 0 (1).

Согласно арифметическим ограничениям ВТФ [1] переменные уравнения (1) взаимно просты:

 (x,y) = (x,z)= (y,z) = 1 (2). 

Для получения дальнейших результатов, определимся, что y кратно e. В доказательстве используются соотношения Барлоу для случая 2 ВТФ [1].

Согласно результатов Барлоу и других исследователей следует существование таких целых чисел: , , , , , , что:

множители :
y + z =  (3) ,

  (4),

т.о.  x = – (5),

множители , (y, e) = e (Случай 2 ВТФ):

x + z = (6),

- … +    (7),

т.о. y = -  (8), при n=0 – имеем Случай 1 ВТФ.

множители :

 =  (9),

 (10),

т.о.   (11).

Для доказательства используем делители числа z. Если выполняются определенные условия в теореме, с таким же успехом, доказательство проводится с помощью делителей числа x.

Подслучай (φ(), e) = e.

Так как по условию (φ(z), e) = e, а z=, сначала рассмотрим случай  (φ(), e) = e (12), затем возможность случая (φ(), e) =1 (13). Если в обоих случаях основное уравнение Ферма не имеет решений, то справедливость теоремы подтверждается.

(9) ⇒ x ≡ - y  mod  (14), (4) ⇒

 / (y + z) = ( - … +  (15),  поэтому:

  mod  (16).  Тогда:

+/(x + y) =

 =  ≡

   mod  (17).

Пусть значение функции Эйлера числа  равно 2ke. В таком случае, возводим в степень φ()/e = 2k левую и правую часть сравнения, чтобы получить значение показателя степени равным значению функции Эйлера числа .

 Возводим в степень 2k левую и правую часть сравнения:

 ≡   mod  (18),

 ≡  ≡ 1 ≡  ≡  mod (19).

Несложно проверить, что это условие эквивалентно условию:
1 ≡  ≡  mod (20).

И это невозможно, т.к. это условие заложено в условие нашей теоремы. Данное условие было “подсмотрено” в доказательстве теоремы Лежандра.

Тем самым, доказан случай - (φ(), e) = e теоремы.

Примеры:

Пусть =31. Тогда φ() = 2*3*5.

Для e=3, (φ(), 3) = 3: =  ≡ 25 (mod 31), т.е. ВТФ справедлива, т.к. соответствует условию теоремы.

Для e=5, (φ(), 5) = 5: =≡1 (mod 31), т.е. не соответствует требованию теоремы, устанавливающему справедливость ВТФ для данного случая.  (Дополнение к примеру:  ≡ 5 (mod 31), ≡ 5 (mod 31), что является альтернативным свойством, использованным Лежандром, при доказательстве теоремы ВТФ для Случая 1).

Примеры чисел, которые “мешают” полному доказательству ВТФ, предложенным способом:

≡ 1 mod (61); ≡ 1 mod (31).

Для простых чисел вида 2ke +1 выполняется ≡ 1 mod (2ke +1), когда:

e =3; k =10, 11, 12, 15, 17;
e =7; k =3;
e =11; k =6;
e =13; k =4, 6;
e =19; k =4.

Подслучай при (φ(), e) =1

Так как (φ(), e) =1, а по предусловию (φ(z), e) = e, то следует, что (φ(), e) = e, т.е. φ() = 2ke (21).

Cгруппируем переменные следующим образом:

 (y+z) + (x+z) – (x+y) = 2z  (22).

Для этого уравнения, согласно соотношений Барлоу для Случая 1 и Случая 2 ВТФ [1], выводятся следующие уравнения:

Случай 1 ВТФ: (y, e) = 1 и  (φ(), e) = e (23):

 = 2z = -  (24),

2z ≡  ≡ 0 mod  (25),

 ≡  mod () (26),

 ≡  ≡ 1 mod () (27), что невозможно по условию 2 теоремы.

Рассмотрим тривиальный пример с использованием простых чисел Софи Жермен. Пусть e – число Софи Жермен. Согласно определению чисел Софи Жермен: 2e +1 – тоже простое число. Рассмотрим, φ() = 2e. На самом деле, мы можем выбрать любой вариант представления числа, но вариант с числом Софи Жермен, является наиболее наглядным, с точки зрения, истории доказательства теоремы. Тогда:

 ≡   mod (=2e+1),

 ≡  1 mod (=2e+1) (28),

≡  1 mod (2e+1) (29),

≡  1 mod (2e+1) (30),

≡  -1 mod (2e+1) (31), возведем в квадрат левую и правую часть, чтобы получить в показателе значение функции Эйлера числа 2e+1:

≡  1 mod (2e+1) (32),

≡  1 mod (2e+1) (33), что невозможно.

{Гипотеза. Для этого случая возможно и другое доказательство - через соотношения Барлоу “второго порядка”, которые можно вывести из сравнения

 ≡ 0 mod  (34).

По методу Барлоу можно получить соотношения и множители для данного сравнения: :

 = –,  = – и  = – (35).

А далее методом, изложенным здесь для подслучая - НОД(φ(), e) = e, выполнить подобное доказательство по модулю .}

Случай 2 ВТФ: НОД(y, e) = e и НОД(φ(), e) = e (36):

 = 2z = -   (37),

≡ - mod  (38),

Возведём левую и правую часть сравнения в степень φ()/e:

≡  mod  (39),

1 ≡  mod  (40).

Однако, ne -1 не делится на e, поэтому 1 ≢  mod ,

≢0 mod  (41).

Рассмотрим ещё один вариант доказательства этого случая, через модуль .

 = 2z = -  (42),

2z ≡  ≡ 0 mod () (43).

Если данное сравнение справедливо, то должно быть справедливым и сравнение:

2z ≡  ≡ 0 mod () (44), справедливость для которого рассмотрена ранее. Т.е. сравнение

  ≡ 0 mod () (45) справедливо тогда и только тогда, когда справедливо сравнение:

 ≡ 0 mod () (46). Однако, как нами доказано, оно не имеет решения, при выполнении условий теоремы.

Т.о., при заданных условиях, теорема справедлива.

Усилить теорему можно, доказав, что ВТФ справедлива и для случая, без выполнения условия 2 теоремы.

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ И ЛИТЕРАТУРЫ

1. P. Ribenboim, Fermat's last theorem for amateurs, Springer-Verlag, New York, NY, 1999.

2. The RSA Cryptosystem against Last Fermat’s Theorem [fermat.2000.ru - http://fermat.2000.ru/fermats/2000ru_vsm_rsa1a_01_04_2010.htm]. // http:// fermat.2000.ru (Data  07.06.2010).

3. RSA [Vikipedia - http://en.wikipedia.org].  – Режим доступа: http://en.wikipedia.org/wiki/RSA (дата обращения 07.01.2010).

4.  Euler's_theorem [Vikipedia - http://en.wikipedia.org].  – Режим доступа:  http://en.wikipedia.org/wiki/Euler's_theorem (дата обращения 07.06.2010).

5.  Криптосистема RSA против ВТФ  [fermat.2000.ru - //
http:// fermat.2000.ru http://www.fermat.2000.ru/fermats/2000ru_vsm_rsa1a_01_04_2010.htm

 (дата обращения - Data 07.06.2010).

6.  “Доказательство ВТФ для n=3 (для любителей)” [fermat.2000.ru - http://www.fermat.2000.ru/fermats/proof_fermat_n3_last_theorem_rus_vakhterov.htm  (дата обращения - Data 07.06.2010).

S.M. Vakhterov,  student, Moscow State Technical University n.a. N.E. Bauman

M.I. Vakhterov, editor

Contact:

http:// fermat.2000.ru/fermats/ case2vtf_version_actual.htm

Last Modified:  August, 19, 2010