Доказательство Великой теоремы Ферма за одну операцию

Page 1

Идея предлагаемого вниманию читателя элементарного доказательства Великой теоремы Ферма исключительно проста: после разложения чисел a, b, c на пары слагаемых, затем группировки из них двух сумм U' и U'' и умножения равенства a^n + b^n - c^n = 0 на 11^n (т.е. на 11 в степени n, а чисел a, b, c на 11) (k+3)-я цифра в числе a^n + b^n - c^n (где k — число нулей на конце числа a + b - c) не равна 0 (числа U' и U'' умножаются по-разному!). Для постижения доказательства нужно знать лишь формулу бинома Ньютона, простейшую формулировку малой теоремы Ферма (приводится), определение простого числа, сложение двух-трех чисел и умножение двузначного числа на 11. Вот, пожалуй, и ВСЁ! Самое главное (и трудное) — не запутаться в десятке цифр, обозначенных буквами. Формальное описание истории теоремы и библиография в русском тексте опущены.

Доказательство приводится в редакции от 1 июня 2005 года (с учетом дискуссии на мехматовском сайте).

В.С.

Элементарное доказательство Великой теоремы Ферма

ВИКТОР СОРОКИН

ИНСТРУМЕНТАРИЙ: [В квадратных скобках приводится поясняющая, не обязательная информация.]

Используемые обозначения:

Все числа записаны в системе счисления с простым основанием n > 10.

[Все случаи с составным n, кроме n = 2^k (который сводится к случаю n = 4), сводятся к случаю

простого n с помощью простой подстановки. Случаи n = 3, 5 и 7 здесь не рассматриваются.]

a_k — k-я цифра от конца в числе a (a₁ — последняя цифра).

[Пример для a = 1043: 1043 = 1x5³ + 0x5² + 4x5¹ + 3x5⁰; a₁ = 3, a₂ = 4, a₃ = 0, a₄ = 1.]

a_(k) — окончание (число) из k цифр числа a (a₍₁₎ = a₁; 1043₍₃₎ = 043). Везде в тексте a₁ № 0.

[Если все три числа a, b и c оканчиваются на ноль, следует разделить равенство 1° на nⁿ.]

(a_iⁿ)₁ = a_i и (a_i^{n — 1})₁ = 1 (см. Малую теорему Ферма для a_i № 0). (0.1°)

(n + 1)ⁿ = (10 + 1)ⁿ = 11ⁿ = …101 (см. Бином Ньютона для простого n).

Простое следствие из бинома Ньютона и малой теоремы Ферма для s № 1 [a₁ № 0]:

если цифра a_s увеличивается/уменьшается на 0 < d < n,

то цифра aⁿ_s+1 увеличивается/уменьшается на d (или d + n, или d - n). (0.2°)

[В отрицательных числах цифры считаются отрицательными.]

***

(1°) Допустим, что aⁿ + bⁿ - cⁿ = 0 .

Случай 1: (bc)₁ ? 0.

(2°) Пусть u = a + b - c, где u_(k) = 0, u_k+1 ? 0, k > 0 [известно, что в 1° u > 0 и k > 0].

(3°) Умножим равенство 1° на число d₁ⁿ (см. §§ 2 и 2a в Приложении) с целью превратить

цифру u_k+1 в 5. После этой операции обозначения чисел не меняются

и равенство продолжает идти под тем же номером (1°).

Очевидно, что и в новом равенстве (1°) u = a + b - c, u_(k) = 0, u_k+1 = 5.

(1*°) И пусть a*ⁿ + b*ⁿ - c*ⁿ = 0, где знаком «*» обозначены записанные в каноническом виде числа в равенстве (1°) после умножения равенства (1°) на 11ⁿ .

(4°) Введем в указанной здесь очередности следующие числа: u, u' = a_(k) + b_(k) - c_(k),

u'' = u — u' = (a — a_(k)) + (b — b_(k)) — (c — c_(k)), v = (a_k+2 + b_k+2 — c_k+2)₁, u*' = a*_(k) + b*_(k) — c*_(k),

u*'' = u* - u*' = (a* - a*_(k)) + (b* - b*_(k)) — (c* - c*_(k)), 11u', 11u'', v* = (a*_k+2 + b*_k+2 — c*_k+2)₁,

и вычислим две последние значащие цифры в этих числах:

(3a°) u_k+1 = (u'_k+1 + u''_k+1)₁ = 5;

(5°) u'_k+1 = (-1, 0 или 1) — так как — n^k < a'_(k) < n^k, — n^k < b'_(k) < n^k, — n^k < c'_(k) < n^k

и числа a, b, c имеют различные знаки;

(6°) u''_k+1 = (4, 5 или 6) (см. 3a° и 5°) [важно: 1 < u''_k+1 < n — 1];

(7°) u'_k+2 = 0 [всегда!] - так как u' < 2n^k ;

(8°) u''_k+2 = u_k+2 [всегда!];

(9°) u''_k+2 = [v + (a_k+1 + b_k+1 - c_k+1)₂]₁, где (a_k+1 + b_k+1 - c_k+1)₂ = (-1, 0 или 1);

(10°) v = [u_k+2 — (a_(k+1) + b_(k+1) - c_(k+1))_k+2]₁ [где (a_(k+1) + b_(k+1) - c_(k+1))_k+2 = (-1, 0 или 1)] =

= [u_k+2 - (-1, 0 или 1)]₁;

(11°) u*_k+1 = u_k+1 = 5 — т.к. u*_k+1 и u_k+1 — последние значащие цифры в числах u* и u;

(12°) u*'_k+1 = u'_k+1 — т.к. u*'_k+1 и u'_k+1 — последние значащие цифры в числах u*' и u';

(13°) u*''_k+1 = (u*_k+1 — u*'_k+1)₁ = (3 — u*'_k+1)₁ = (4, 5 или 6) [важно: 1 < u*''_k+1 < n — 1];

(14°) (11u')_k+2 = (u'_k+2 + u'_k+1)₁ (затем — в результате приведения чисел к каноническому виду ;

величина u'_k+1 «уходит» в u*''_k+2, поскольку u*'_k+2 = 0);

(14a°) важно: числа (11u')_(k+2) и u*'_(k+2) отличаются только k+2-ми цифрами, а именно:

u*'_k+2 = 0, но (11u')_k+2 № 0 в общем случае;

(15°) (11u'')_k+2 = (u''_k+2 + u''_k+1)₁;

(16°) u*_k+2 = (u_k+2 + u_k+1)₁ = (u''_k+2 + u_k+1)₁ = (u''_k+2 + 5)₁;

(16а°) к сведению: u*'_k+2 = 0 (см. 7°);

(17°) u*''_k+2 = (u*_k+2 +1, u*_k+2 или u*_k+2 — 1)₁ = (см. 9°) = (u''_k+2 + 4, u''_k+2 + 5 или u''_k+2 + 6)₁;

(18°) v* = [u*_k+2 — (a*_(k+1) + b*_(k+1) — c*_(k+1))_k+2]₁

[где u*_k+2 = (u_k+2 + u_k+1)₁ (см. 16°), а (a*_(k+1) + b*_(k+1) — c*_(k+1))_k+2 = (-1, 0 или 1) — см. 10°] =

= [(u_k+2 + u_k+1)₁ — (-1, 0 или 1)]₁.

(19°) Введем числа U' = (a_k+1)ⁿ + (b_k+1)ⁿ — (c_k+1)ⁿ, U'' = (aⁿ + bⁿ — cⁿ) — U', U = U' + U'',

U*' = (a*_k+1)ⁿ + (b*_k+1)ⁿ — (c*_k+1)ⁿ, U*'' = (a*ⁿ + b*ⁿ — c*ⁿ) — U*', U* = U*' + U*'';

(19а°) к сведению: U'_(k+1) = U*'_(k+1) = 0.

(20°) Лемма: U_(k+2) = U'_(k+2) = U''_(k+2) = U*_(k+2) = U*'_(k+2) = U*''_(k+2) = 0 [всегда!].

Действительно, из 1° мы имеем:

U = aⁿ + bⁿ — cⁿ =

= (a_(k+1) + n^k+1a_k+2 + n^k+2P_a)ⁿ + (b_(k+1) + n^k+1b_k+2 + n^k+2P_b)ⁿ — (c_(k+1) + n^k+1c_k+2 + n^k+2P_c)ⁿ =

= (a_(k+1)ⁿ + b_(k+1)ⁿ — c_(k+1)ⁿ) + n^k+2(a_k+2a_(k+1)^{n — 1} + b_{k+2b (k+1)}^{n — 1} — c_{k+2c (k+1)}^{n — 1}) + n^k+3P =

= U' + U'' = 0, где

U' = a_(k+1)ⁿ + b_(k+1)ⁿ — c_(k+1)ⁿ,

(20a°) U'' = n^k+2(a_k+2a_(k+1)^n -1 + b_{k+2b (k+1)}^n -1 — c_{k+2c (k+1)}^n -1) + n^k+3P,

где (a_k+2a_(k+1)^n -1 + b_k+2b_(k+1)^n -1 — c_k+2c_(k+1)^n -1)₁ = (см. 0.1°)=

(20b°) = (a_k+2 + b_k+2 — c_k+2)₁ = U''_k+3 = v (см. 4°).

(21°) Следствие: (U'_k+3 + U''_k+3)₁ = (U*'_k+3 + U*''_k+3)₁ = 0.

(22°) Вычислим цифру (11ⁿU')_k+3:

[так как числа (11u')_(k+2) и u*'_(k+2) отличаются только k+2-ми цифрами на величину

(11u')_k+2), то на эту величину будут отличаться и цифры (11ⁿU')_k+3 и U*'_k+3, это означает,

что цифра (11ⁿU')_k+3 будет на (11u')_k+2 превышать цифру U*'_k+3 (см. 0.2°)]

(11ⁿU')_k+3 = U'_k+3 = (U*'_k+3 + (11u')_k+2)₁ = (U*'_k+3 + u'_k+1)₁.

(23°) Откуда U*'_k+3 = U' _k+3 — u'_k+1.

(24°) Вычислим цифру U*'' _k+3 :

U*'' _k+3 = v* = (u_k+2 + u_k+1)₁ — (-1, 0 или 1) — см. (18°);

(25°) Наконец, вычислим цифру (U*'_k+3 + U*''_k+3)₁:

(U*'_k+3 + U*''_k+3)₁ = (U*'_k+3 + U*''_k+3 — U'_k+3 — U''_k+3)₁ = (U*'_k+3 — U'_k+3 + U*''_k+3 — U''_k+3)₁ =

(см. 23° и 24°) = (- u'_k+1 + v* - v) = (см. 18° и 10°) =

= (- u'_k+1 + [u_k+2 + u_k+1 — (-1, 0 или 1)] — [u_k+2 - (-1, 0 или 1)])₁ =

= (- u'_k+1 + u_k+1 + (-2, —1, 0, 1, или 2))₁ = (см. 3a°) =

( u''_k+1 + (-2, —1, 0, 1, или 2))₁ = (см. 6°) = (2, 3, 4, 5, 6, 7 или 8) № 0,

что противоречит 21° и, следовательно, выражение 1° есть неравенство.

Случай 2 [доказывается аналогично, но намного проще]: b (или c) = n^tb', где b₁ = 0 и b_t+1 = b'₁ № 0.

(26°) Введем число u = c - a > 0, где u_{(nt — 1)} = 0, а u_nt ? 0 (см. § 1 в Приложении).

(27°) После умножения равенства 1° на число d₁ⁿ (с целью превратить цифру u_nt в 5)

(см. §§ 2 и 2a в Приложении) обозначения чисел сохраняются.

(28°) Пусть: u' = a_{(nt — 1)} - c_{(nt — 1)}, u'' = (a - a_{(nt — 1)}) — (c - c_{(nt — 1)}) (где, очевидно, u''_nt = (a_nt - c_nt)₁);

U' = a_(nt)ⁿ + bⁿ - c_(nt)ⁿ (где U'_{(nt + 1)} = 0 — см. 1° и 26°), U'' = (aⁿ - a_(nt)ⁿ) — (cⁿ - c_(nt)ⁿ),

U*' = a*_(nt)ⁿ + b*ⁿ - c*_(nt)ⁿ (где U*'_{(nt + 1)} = 0), U*'' = (a*ⁿ - a*_(nt)ⁿ) — (c*ⁿ - c*_(nt)ⁿ),

v = a_nt+1 — c_nt+1.

Вычисления, полностью аналогичные вычислениям в случае 1, показывают, что nt+2-я цифра в равенстве Ферма не равна нулю. Число b во всех расчетах (кроме самой последней операции и в п. 27°) можно проигнорировать, т.к. цифры bⁿ_nt+1 и bⁿ_nt+2 при умножении равенства 1° на 11ⁿ не меняются (т.к. 11ⁿ₍₃₎ = 101).

Таким образом, для простых n > 7 теорема доказана.

==================

ПРИЛОЖЕНИЕ

§ 1. Если числа a, b, c не имеют общих сомножителей и b₁ = (c - a)₁ = 0,

тогда из числа R = (cⁿ - aⁿ)/(c - a) =

= c^n -1 + c^n -2a + c^n -3a² + … c²a^{n — 3} + ca^{n — 2} + a^{n — 1} =

= (c^n -1 + a^n -1) + ca (c^n -3 + a^n -3) + … + c^(n -1)/2a^(n -1)/2 =

= (c^n -1 — 2c^(n -1)/2a^(n -1)/2 + a^n -1 + 2c^(n -1)/2a^(n -1)/2) + ca (c^n -3 — 2c^(n -3)/2a^(n -3)/2 + a^n -3 + 2c^(n -3)/2a^(n -3)/2) +

+ … + c^{(n -1)/2}a^{(n -1)/2} = (c - a)²P + nc^{(n -1)/2}a^{(n -1)/2} следует, что:

c - a делится на n², следовательно R делится на n и не делится на n²;

так как R > n, то число R имеет простой сомножитель r не равный n;

c - a не делится на r;

если b = n^tb', где b'₁ № 0, то число c — a делится на n^{tn — 1} и не делится n^tn.

§ 2. Лемма. Все n цифр (a₁d_i)₁, где d_i = 0, 1, … n — 1, различны.

Действительно, допустив, что (a₁d₁*)₁ = (a₁d₁**)₁, мы находим: ((d₁* - d₁**)a₁)₁ = 0.

Откуда d₁* = d₁**. Следовательно, множества цифр a₁ (здесь вместе с a₁ = 0) и d₁ совпадают.

[Пример для a₁ = 2: 0: 2x0 = 0; 1: 2x3 = 11; 2: 2x1 = 2; 3: 2x4 = 13; 4: 2x2 = 4.

При составном n Лемма несправедлива: в базе 10 и (2×2)₁ = 4, и (2×7)₁ = 4.]

§ 2a. Следствие. Для любой цифры a₁ № 0 cуществует такая цифра d_i, что (a₁d_i)₁ = 1.

[Пример для a₁ = 1, 2, 3, 4: 1x1 = 1; 2x3 = 11; 3x2 = 11; 4x4 = 31.]

ВИКТОР СОРОКИН

e-mail: victor. sorokine@wanadoo.fr

4 ноября 2004, Франция

P. S. Доказательство для случаев n = 3, 5 , 7 аналогично, но в (3°) цифра u_k+1 превращается не в 5, а в 1, и в (1*°) равенство (1°) умножается не на 11ⁿ, а на некоторое hⁿ, где h — некоторое однозначное число.