[Из песочницы] Гипотеза Била или как заработать миллион долларов и познать энтропию
Математика — прекрасная и очень красивая наука с множеством областей, теорий и ответвлений. Однако есть в ней особая, «чистая» область, этакая математика в квадрате, под названием высшая арифметика. А уже там прячется основа основ всей математики, её священный Грааль — элементарная теория чисел, изучающая без использования методов других разделов математики такие вопросы как делимость целых чисел, проблема факторизации, диофантовы уравнения и многое другое. Одну из открытых проблем этой теории, гипотезу Била, я доказал и сегодня вам это покажу.
Что это за зверь? Гипотеза Била — предложенное в 1993 году математиком-любителем Эндрю Билом (Andrew Beal) утверждение со следующей формулировкой: если $inline$A^x + B^y = C^z$inline$, где $inline$A, B, C, x, y, z$inline$ — натуральные числа и $inline$ x, y, z > 2$inline$, то $inline$A, B, C$inline$ имеют общий простой делитель. Казалось бы всё просто, но это только на первый взгляд. Эта задача сложна настолько, что за её доказательство (или опровержение) Бил учредил премию в один миллион долларов. Звучит заманчиво? Очень. На этом вступление будем считать законченным и перейдём непосредственно к доказательству.
К энтропии
Что есть энтропия? Не пугайтесь, этот вопрос в рамках данной статьи мы рассматривать не будем. Просто взглянем на числа $inline$A^x, B^y$inline$ как на две независимые системы с энтропией $inline$H_A = log_q A^x, H_B = log_q B^y$inline$ соответственно. Можем ли мы сделать это? Конечно. По теореме сложения энтропии при объединении независимых систем их энтропии складываются. Следовательно, энтропия сложной системы $inline$C^z$inline$ равна нолю, так как
$$display$$ H (C^z) = H (A^x) + H (B^y) \\ log_2 C^z = log_2 A^x + log_2 B^y \\ log_2 C^z = log_2 A^x B^y \\ C^z = A^x B^y \\ \left\{ \begin{array}{rcl} C^z = A^x B^y \\ C^z = A^x + B^y \\ \end{array} \right. $$display$$
при $inline$x, y > 2$inline$ имеет только тривиальное решение. А значит у системы $inline$C^z$inline$ возможно только одно состояние. Или, говоря простым языком, $inline$C^z$inline$ представимо в виде суммы $inline$A^X + B^y$inline$ единственным образом с точностью до перестановки слагаемых. Запомним этот факт, мы вернёмся к нему позже.
D значит Dелимость
Введём понятие коэффициента делимости $inline$D$inline$. Пусть $inline$B^y = b^{v_1}_1 b^{v_2}_2 … b^{v_i}_i $inline$ — каноническое разложение числа $inline$B^y$inline$ на множители, $inline$s$inline$ — число десятков числа $inline$\frac{B^y}{b^{v_i}_i}$inline$, записанного в системе счисления по основанию $inline$b^{v_i}_i$inline$, $inline$k, d \in \mathbb{N}$inline$ тогда $inline$D$inline$ является решением системы
$$display$$ \left \{ \begin{array} {rcl} 0 < k < 10 \\ 0 < d < 10 \\ D = k \cdot s + d \\ 10 \cdot D \equiv 1 \mod b^{v_1}_1 b^{v_2}_2 ... b^{v_{i-1}}_{i-1} \\ \end{array} \right. $$display$$
Лемма 1: $inline$D$inline$ существует для любых чисел, взаимно простых с основанием системы счисления в которой это число записано. Доказательство леммы 1 следует из того факта, что уравнение $inline$a \cdot x + b \cdot y = 1$inline$ всегда имеет решение.
Теорема 1 (теорема Громовой): число $inline$P$inline$ делится на $inline$T$inline$, если число $inline$P$inline$ без $inline$n$inline$ последних цифр плюс $inline$n$inline$ последних цифр, умноженных на $inline$D^n$inline$, делится на $inline$T$inline$.
Данная теорема была впервые сформулирована российским математиком Людмилой Фёдоровной Громовой не позднее 2009 года и я познакомился с ним в этой работе. Доказательство теоремы 1 несложно, но весьма громоздко, поэтому здесь приведено не будет, интересующимся математикой читателям предлагаю доказать её самостоятельно, остальным — прослушать аудио версию доказательства за авторством Александра Александровича Дегтяря.
Per aspera ad astra
Докажем гипотезу Била от противного. Допустим, что числа $inline$A^x, B^y, C^z$inline$ попарно взаимно просты. Не теряя общности, можем считать $inline$B^y
Запишем числа $inline$A^x, C^z$inline$ в виде $inline$\overline{a_0a_1}, \overline{c_0, c_1}$inline$, где $inline$a_1, c_1$inline$ — первые $inline$y$inline$ цифр, считая справа, $inline$a_0, c_0$inline$ — остальные цифры. Нетрудно увидеть, что $inline$a_1 = c_1, c_0 = a_0 +1$inline$, т.е. вся разница между $inline$A^x, C^z$inline$ заключается в том, что в одном разряде у них стоят отличающиеся на единицу цифры. Следовательно, $inline$D_{C^z} = D_{A^x} + 1$inline$, т.е. коэффициенты делимости $inline$A^x, C^z$inline$ тоже отличаются на $inline$1$inline$.
Делится ли $inline$A^x, C^z$inline$ на $inline$A^x, C^z$inline$ соответственно? Глупый вопрос, конечно же делится. Следовательно, по теореме Громовой,
$$display$$ \left \{ \begin{array} {rcl} c_0 + c_1D_{C^z}^y = C^z\\ a_0 + a_1D_{A^x}^y = A^x\\ \end{array} \right. $$display$$
Преобразуем и вычтем второе уравнение из первого:
$$display$$ \left \{ \begin{array} {rcl} a_0 +1 + a_1(D_{A^x}^y + 1) = C^z\\ a_0 + a_1D_{A^x}^y = A^x\\ \end{array} \right. $$display$$
$$display$$10^y = a_1((D_{A^x} + 1)^y — D_{A^x}^y) +1$$display$$
Нетрудно увидеть, что при $inline$D = 0$inline$ уравнение имеет множество решений. Но по определению $inline$D$inline$ может быть равен нолю только для $inline$1$inline$, значит $inline$A^x = 1$inline$. Следовательно, по теореме Михалеску $inline$z = 2$inline$, но по определению $inline$z > 2$inline$. Противоречие.
А теперь внимание! Фокус! Следите за руками!!!
Ловкость рук, никакого мошенства и немного магии энтропии
Так как энтропия сложной системы $inline$H (C^z) = 0$inline$, то для $inline$C^z$inline$ числа $inline$A^x, B^y$inline$, а значит и $inline$y, a_1, D_{A^x}$inline$ определены однозначно. Следовательно, уравнение $inline$10^y = a_1((D_{A^x} + 1)^y — D_{A^x}^y) +1$inline$ не имеет переменных и является не уравнением, а равенством, и может иметь лишь единственное решение, которое вводит нас в противоречие с условием гипотезы Била. Следовательно, наше допущение ложно и $inline$A^x, B^y, C^z$inline$ имеют общий простой делитель.
Доказано.
Литература: Л.Ф. Громова, Признаки делимости чисел с окончаниями 1, 3, 7, 9
P.S. Используя удивительные свойства энтропии вычислительную сложность задачи факторизации можно снизить с $inline$2^n$inline$ до $inline$n^{2 lnA lnB lnC}$inline$. Я нашёл этому поистине чудесное доказательство, которое, однако, выходит далеко за рамки этого поста. Мы поговорим об этом в другой раз.
