Математика — прекрасная и очень красивая наука с множеством областей, теорий и ответвлений. Однако есть в ней особая, «чистая» область, этакая математика в квадрате, под названием высшая арифметика. А уже там прячется основа основ всей математики, её священный Грааль — элементарная теория чисел, изучающая без использования методов других разделов математики такие вопросы как делимость целых чисел, проблема факторизации, диофантовы уравнения и многое другое. Одну из открытых проблем этой теории,
гипотезу Била, я доказал и сегодня вам это покажу.
Что это за зверь? Гипотеза Била — предложенное в 1993 году математиком-любителем Эндрю Билом (Andrew Beal) утверждение со следующей формулировкой: если
, где
— натуральные числа и
, то
имеют общий простой делитель. Казалось бы всё просто, но это только на первый взгляд. Эта задача сложна настолько, что за её доказательство (или опровержение) Бил учредил премию в
один миллион долларов. Звучит заманчиво? Очень. На этом вступление будем считать законченным и перейдём непосредственно к доказательству.
К энтропии
Что есть энтропия? Не пугайтесь, этот вопрос в рамках данной статьи мы рассматривать не будем. Просто взглянем на числа
как на две независимые системы с энтропией
соответственно. Можем ли мы сделать это? Конечно. По теореме сложения энтропии при объединении независимых систем их энтропии складываются. Следовательно, энтропия сложной системы
равна нолю, так как
при
имеет только тривиальное решение. А значит у системы
возможно только одно состояние. Или, говоря простым языком,
представимо в виде суммы
единственным образом с точностью до перестановки слагаемых. Запомним этот факт, мы вернёмся к нему позже.
D значит Dелимость
Введём понятие коэффициента делимости
. Пусть
— каноническое разложение числа
на множители,
— число десятков числа
, записанного в системе счисления по основанию
,
тогда
является решением системы
Лемма 1:
существует для любых чисел, взаимно простых с основанием системы счисления в которой это число записано. Доказательство леммы 1 следует из того факта, что уравнение
всегда имеет решение.
Теорема 1 (теорема Громовой): число
делится на
, если число
без
последних цифр плюс
последних цифр, умноженных на
, делится на
.
Данная теорема была впервые сформулирована российским математиком Людмилой Фёдоровной Громовой не позднее 2009 года и я познакомился с ним в
этой работе. Доказательство теоремы 1 несложно, но весьма громоздко, поэтому здесь приведено не будет, интересующимся математикой читателям предлагаю доказать её самостоятельно, остальным — прослушать
аудио версию доказательства за авторством Александра Александровича Дегтяря.
Per aspera ad astra
Докажем гипотезу Била от противного. Допустим, что числа
попарно взаимно просты. Не теряя общности, можем считать
Тогда, перейдя в систему счисления по основанию
, гипотеза принимает вид
. По лемме
вычислим для
.
Запишем числа
в виде
, где
— первые
цифр, считая справа,
— остальные цифры. Нетрудно увидеть, что
, т.е. вся разница между
заключается в том, что в одном разряде у них стоят отличающиеся на единицу цифры. Следовательно,
, т.е. коэффициенты делимости
тоже отличаются на
.
Делится ли
на
соответственно? Глупый вопрос, конечно же делится. Следовательно, по теореме Громовой,
Преобразуем и вычтем второе уравнение из первого:
Нетрудно увидеть, что при
уравнение имеет множество решений. Но по определению
может быть равен нолю только для
, значит
. Следовательно, по
теореме Михалеску , но по определению
. Противоречие.
А теперь внимание! Фокус! Следите за руками!!!
Ловкость рук, никакого мошенства и немного магии энтропии
Так как энтропия сложной системы
, то для
числа
, а значит и
определены однозначно. Следовательно, уравнение
не имеет переменных и является не уравнением, а равенством, и может иметь лишь единственное решение, которое вводит нас в противоречие с условием гипотезы Била. Следовательно, наше допущение ложно и
имеют общий простой делитель.
Доказано.
Литература: Л.Ф. Громова,
Признаки делимости чисел с окончаниями 1, 3, 7, 9
P.S. Используя удивительные свойства энтропии вычислительную сложность задачи факторизации можно снизить с
до
. Я нашёл этому поистине чудесное доказательство, которое, однако, выходит далеко за рамки этого поста. Мы поговорим об этом в другой раз.
комментарии (101)