Главная > Математика > Введение в теорию чисел. Алгоритм RSA
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

§ 5.6. Диофантовы уравнения

Ниже мы используем сравнения для доказательства отсутствия решений у некоторых Диофантовых уравнений. Диофантов о уравнение — это полиномиальное уравнение с несколькими неизвестными и целыми коэффициентами. Примеры: Когда говорят о решениях диофантова уравнения, обычно имеют в виду целочисленные решения. Эти уравнения названы по имени греческого математика Диофанта из Александрии, жившего около 250 г. н. э. В своей «Арифметике» Диофант подробно

обсуждает проблему поиска решений неопределенных уравнений. Однако он искал рациональные решения, а не целые, что мы обычно делаем сегодня.

Поскольку эти уравнения зависят от нескольких переменных, они могут иметь бесконечно много решений. Например, для любого целого к числа удовлетворяют уравнению Уравнение частный случал великой Теоремы Ферма, о которой рассказывалось во введении и конце второй главы. Как мы видели, если целые числа, удовлетворяющие этому уравнению, то одно из них должно быть равно нулю. Это специальный случай теоремы, впервые доказанный Эйлером в 1770 году. Вспомните, что Ферма сформулировал свою великую Теорему на полях принадлежащей ему копии Диофантовой «Арифметики».

Уравнение имеет более недавнюю и простую историю. В статье, написанной в 1969 году, Льюис (D. J. Lewis) показал, что это уравнение не может иметь более 18 целочисленных решений. Два года спустя Р. Финкелыптейн (R. Finkel-stein) и X. Лондон (Н. London) наконец доказали, что это уравнение не имеет ни одного целого решения. Их доказательство коротко: оно занимает только страницу 111 четырнадцатого тома «Канадского Математического Бюллетеня», но отнюдь не элементарно. Однако, в 1973 году Халтер-Кох (F. Halter-Koch) и Удреско (V. St. Udresco) независимо дали доказательство отсутствия у этого уравнения решений, которое использует только сравнения по модулю 9. Именно его мы сейчас подробно опишем.

Доказательство «от противного». Предположим, что уравнение имеет целочисленное решение, т.е. существуют такие целые что Так как все числа в этом выражении целые, мы можем рассмотреть его по модулю 9. Число 117 делится на 9, поэтому

Следовательно, если это уравнение имеет целое решение

то Возможно ли это? Чтобы разобраться, напомним: каждое целое число по модулю 9 имеет вычет, лежащий между 0 и 8. Значит нам будет достаточно вычислить кубы по модулю 9 каждог о из этих вычетов.

(см. скан)

Простой взгляд на таблицу показывает, что вычет куба целого числа по модулю 9 может быть равен только 0, 1 или 8. В частности, нет такого целого куб которого сравним с 5 по модулю . Следовательно, не может иметь целочисленных решений, что и требовалось доказать.

Можно извлечь такую мораль из этого примера: первое доказательство теоремы часто оказывается и не самым простым, и не самым элегантным. Так бывает потому, что первое доказательство обычно находится исследователем, «вспахивающим целину» неизученного. Со временем связь между новыми методами и ближайшими областями становится яснее, что делает возможным находить более короткое, простое и прямое доказательство, чем первое. Пример, который мы разобрали, довольно наивен, но, конечно, он не лишает законной силы сделанного нами вывода. Как однажды сказал математик А. С. Безикович (A. S. Besicovitch), «репутация математика держится на том, сколько он дал некрасивых доказательств».

<< Предыдущий параграф Следующий параграф >>
Оглавление