§ 1.7. Теоремы и доказательства

Как мы уже говорили, цель нашей книги — подробное изложение математических основ системы шифрования RSA. Разработка ее математического хребта была завершена к концу девятнадцатого века усилиями древнегреческих математиков, Ферма, Эйлера и Гаусса. Однако еще 20 лет назад большинство приложений оставалось неизвестными, а некоторые теоремы, которые мы будем упоминать, появились лишь в последние годы.

Многие из приводимых здесь результатов не будут для Вас новыми. К их числу относятся, например, способ вычисления наибольшего общего делителя, основанный на последовательных делениях, а также простейшие процедуры разложения на простые множители. Новизна может заключаться, однако, в самом подходе, поскольку мы доказываем каждое утверждение, включая и корректность вычислительных процедур, исходя из первичных принципов.

Математика древнего Египта и Месопотамии представляла собой набор правил для решения практических задач. Только ее объединение с греческой философией превратило ее в современную теоретическую науку. Первые греческие математики — Фалес (Thales) и Пифагор (Pythagoras) - были также знаменитыми философами. Представление о том, что математический факт можно доказывать, произросло из взаимодействия с философией. Помимо всего прочего, доказательство — это просто рассуждение, которое выводит некоторое утверждение из других, уже известных. А рассуждать греческие философы любили!

Около 400 года до н. э. греческие математики почувствовали необходимость в более или менее точной формулировке

предположений, лежащих в основе их работы. Поэтому и Эвклид открывает свои «Начала» со строгих определений и аксиом, на которых базируются его доказательства. Например, в начале первой книги он определяет точку, прямую, плоскость, поверхность и т.д. Затем он формулирует аксиомы, истинность которых он считает самоочевидной. Аксиомы объясняют связи между ранее введенными объектами. Затем он показывает, каким образом гораздо более сложные факты об изучаемых объектах сводятся, путем логических рассуждений, к аксиомам. Главное достоинство его подхода состоит в придании основательности всему зданию. Если фундамент достаточно прочный, то и все здание может возноситься высоко без опасения, что оно рухнет под собственным весом.

Математический факт обычно называется теоремой. Это греческое слово исходно означало «наблюдение, теория». Его современное значение «доказываемое утверждение» восходит по меньшей мере к эвклидовым «Началам». Утверждение теоремы часто принимает вид условного утверждения:

если выполняется некоторое предположение, то справедливо некоторое заключение.

Доказательство такой теоремы представляет собой логическое рассуждение, которое показывает, как заключение вытекает из предположения. Приведем пример:

Теорема 1. Если а — четное целое число, то число тоже четное.

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

что «базисные свойства» действительно элементарны и Вы их хорошо знаете. Сюда входят, например, правила сложения и умножения целых чисел, а также утверждение о том, что между любыми двумя целыми числами есть лишь конечное множество целых чисел. Воспользуемся этими свойствами для доказательства приведенной выше теоремы.

Доказательство теоремы 1. Предположение теоремы о четности а означает, что а делится на 2, см. § 3.1. Поэтому должно существовать такое число что Возводя в квадрат последнее равенство, получаем

Поэтому число также делится на 2. Другими словами, число четное, что и является заключением теоремы.

Теорема 1 показывает, что из факта четности числа о вытекает, факт четности его квадрата. Обратным к условному утверждению «из А следует В» является условное утверждение «из В следует А». Значит утверждение, обратное к теореме 1, звучит так: если целое число четное, то и а — четное целое число. Заметим, что если само утверждение истинно, то это ничего не говорит нам об истинности обратного утверждения. Например, для истинного утверждения если целое число делится на 4, то оно четное, обратное утверждение ложно: число 6 четное, однако на 4 оно не делится. Если оба утверждения «из А следует В» и «из В следует А» истинны, то мы говорим, что эквивалентны. Эквивалентность обычно записывается в виде: «А выполняется, если и только если выполняется В». Таким образом, мы приходим к следующей теореме.

Теорема 2. Целое число а четное, если и только если тоже четное.

Мы уже доказали, что если о четное, то и тоже четное. Теперь мы должны доказать обратное утверждение. Прежде

перейти к доказательству, обсудим еще один логический момент. Обозначим отрицание утверждения через не Например, отрицание не утверждения Р: «число а четное» имеет вид «число нечетное». Пусть теперь два утверждения. Утверждение: «из не следует не называется противоположным к утверждению из следует Любое утверждение истинно, если и только если его противоположное тоже истинно. Подобное высказывание выглядит сомнительно только потому, что оно выражено на непривычном языке. Но представим себе следующую историю. Друг, приглашенный Вами на вечеринку, говорит: «Моя машина сломана, однако если ее вовремя починят, то я приеду». Если теперь Ваш друг не приезжает на вечеринку, то Вы заключаете, что его машину вовремя не починили, а это и есть противоположное к утверждению Вашего друга.

Вернемся к доказательству теоремы 2.

Доказательство теоремы 2. Мы уже видели, что если число о четное, то и число четное. Осталось доказать, что если четное, то и о будет четным. Вместо последнего утверждения мы будем доказывать противоположное ему, т.е. утверждение «если число о нечетное, то и нечетное». Однако целое число, не являющееся четным, нечетно. Более того, всякое нечетное целое число представимо в виде «четное . Поэтому для нечетного о существует целое число при котором Возводя в квадрат обе части последней формулы, мы получаем

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

Теорема 1 была сформулирована в виде «если о четно, то и четно». Это означает, на самом деле, что квадрат любого четного числа четен. Другими словами, мы доказываем

справедливость утверждения для всех четных чисел. Рассмотрим теперь утверждение «всякое четное число делится на 4». Мы снова указываем на общее свойство всех четных чисел, однако на сей раз утверждение оказывается ложным. Почему? Например, потому, что число 6 четное, однако на 4 оно не делится. Таким образом, утверждение о том, что какое-то свойство присуще всем элементам некоторого множества, можно опровергнуть, предъявив элемент, для которого оно не выполняется. Такой элемент называется контрпримером к утверждению.

Не всегда утверждение теоремы записывается в приведенном выше условном виде. Иногда, например, утверждается, что объект с заданными свойствами существует. Так, для любого вещественного числа х существует такое целое число что Самый естественный способ доказательства подобных теорем состоит в предъявлении явного метода для нахождения такого объекта. Если в приведенном выше примере обозначить целую часть числа х через то является целым числом, большим х, и мы можем положить Предположив теперь, что десятичное представление числа х известно, мы легко найдем с помощью описанного метода. Однако подобные утверждения можно доказывать и не указывая способа построения объекта. Такое доказательство называется неконструктивным доказательством существования. Оно не настолько таинственно, как может показаться. Мы знаем, например, что в любой компании из 400 человек есть двое с совпадающим днем рождения, поскольку Хотя такое рассуждение и верно, оно не дает нам способа найти таких двух человек; значит это неконструктивное доказательство существования.

Большинство книг по теории чисел широко используют неконструктивные доказательства даже при наличии

конструктивных. Это не просто вопрос вкуса: часто конструктивные доказательства выглядят гораздо более неуклюже, чем аналогичные доказательства чистого существования, а для математиков элегантность значит не меньше, чем для художников. В этой книге мы будем, однако, по мере сил избегать неконструктивных доказательств. Такой подход объясняется, в первую очередь, тем, что нас интересуют приложения в криптографии. Поэтому не достаточно просто знать, что у составного числа есть нетривиальный множитель, нужно уметь его отыскивать.

Эти краткие заметки должны позволить Вам приступить к чтению. Методы доказательств будут подробнее разобраны ниже, прежде всего в § 3.7 и § 6.2. Однако необходимо с самого начала понять, что искусство доказательства теорем следует заботливо взращивать, и лучший способ выращивания — частое упражнение. Когда Птолемей, царь египетский, спросил Эвклида, нет ли более простого способа изучения геометрии, чем штудирование «Начал», ответ математика гласил: «В геометрии нет царской дороги». Истинное во времена Эвклида, это утверждение сохраняет свою справедливость и по сей день.