Текст книги "Путеводитель для влюбленных в математику"

Применение простых чисел в криптографии

Изучение простых чисел относится к области математики под названием теория чисел. Британский математик Годфри Харди говорил: «До сих пор никто не обнаружил, как применить теорию чисел в военных целях».

Харди не мог предвидеть появления глобальной компьютерной сети и того факта, что безопасность в сети будет зависеть от простых чисел. Каким образом?

Пусть P и Q – два больших простых числа, скажем стозначных. Перемножить их – титанический труд для человека, но компьютер может посчитать произведение N = P × Q мгновенно. В то же время мы угодим в тупик, если попытаемся выяснить, какие два простых множителя дают N при умножении. Никто не знает эффективного алгоритма разложения таких огромных чисел на простые множители[25]25
  Дадим зарок не пользоваться ничем, кроме карандаша и бумаги, и попробуем самостоятельно убедиться в том, что перемножать простые числа сравнительно легко, а раскладывать их произведение на множители – сложно. Для начала умножим 227 на 281. Если ни на что не отвлекаться, можно найти шестизначный ответ за пару минут. А теперь попробуйте найти без калькулятора два трехзначных простых множителя числа 211 591. Это не так-то просто. Ответ будет в конце главы.


[Закрыть].

(Как это ни странно, определить, простое число или составное, можно достаточно быстро; однако найти простые множители больших чисел совсем не просто.)

Удивительно, однако эта диспропорция – легко перемножить, сложно разложить на множители – легла в основу создания шифров. Криптографическая система с открытым ключом[26]26
  Термин «открытый ключ» означает, что раскрытие алгоритма шифрования – ключ к нему находится в открытом доступе – еще не рассекречивает сообщение. Один из таких алгоритмов изобрели в 1970-е Рон Ривест (Ron Rivest), Ади Шамир (Adi Shamir) и Леонард Адлеман (Leonard Adleman); по первым буквам их фамилий метод назвали RSA.


[Закрыть] устроена так, что можно раскрыть метод шифровки сообщений, но это не облегчит расшифровку засекреченных текстов. Мы не станем сейчас погружаться в детали метода, но основная идея состоит в том, что в процессе шифрования используется составное число N, представляющее собой произведение двух огромных простых чисел: N = P × Q. Расшифровка требует знания конкретных простых чисел P и Q. Если мы знаем N, этого достаточно для шифровки, но не для декодирования, а найти его простые множители все еще чрезвычайно сложно.

Мы используем криптографическую систему с открытым ключом всякий раз, когда совершаем покупки в интернете. Прежде чем браузер вышлет продавцу номер нашей кредитной карты, он получает от продавца открытый ключ шифрования. Браузер шифрует номер карты с помощью метода, о котором мы рассказывали. Если перехватить ключ, это ничего не даст, потому что метод шифровки не говорит о методе расшифровки (а его знает только продавец). Когда зашифрованное сообщение приходит на компьютер продавца, индивидуальный метод расшифровки раскрывает номер карты лишь законному получателю информации.

Криптографическая система с открытым ключом имеет и военные применения, вплоть до системы приведения в боевую готовность ядерного оружия[27]27
  Криптографические системы на основе перемножения простых чисел будут эффективны лишь до тех пор, пока ученые не усовершенствуют квантовые компьютеры, где логические элементы (кубиты) могут находиться в состоянии 0 и 1 одновременно. Теоретически так называемый алгоритм Шора с помощью квантового компьютера способен разложить большое число на простые множители почти так же быстро, как происходит само шифрование. – Прим. пер.
  Несмотря на то что математики уже больше ста лет знают, что решение задачи о трисекции угла с помощью слепой линейки и циркуля невозможно, все время находятся энтузиасты, предлагающие очередное «решение». Анализ самых остроумных попыток можно найти в книге Андервуда Дадли «Смета трисекций» (A Budget of Trisections).
  Один из них равен – i, потому что (– i) × (– i) × (– i) = (– i)³ = i. Но чему равны другие два? Ответ вы найдете в конце главы.


[Закрыть].

Решение задачи о разложении на множители

211 591 = 457 × 463.

Глава 2
Двоичная система счисления[28]28
  Популярный слоган на футболке математика: «Все люди делятся на 10 категорий: те, кто понимает двоичную систему счисления, и те, кто в ней ничего не смыслит». Когда вы прочтете эту главу, вы тоже сможете шутить в этом духе.


[Закрыть]

Однажды в Риме

Древних римлян часто поминают дурным словом за их громоздкую систему записи чисел. Люди не любят римские числа, так как они обременяют вычисления. Никто не обрадуется перспективе перемножать XLVII и DCDXXIV. А вот задача умножить 47 на 924 не выглядит настолько угрожающей (хотя большинство из нас все равно побежит за калькулятором).

Впрочем, прежде чем сбрасывать римские числа со счетов как причудливый анахронизм, нам необходимо признать, что их основополагающий принцип – буквы вместо цифр – используется до сих пор. Этот ключевой аспект римских чисел обрел новое воплощение. Что легче прочесть?

• Реновация школ в нашем округе обойдется в 23000000 долларов.

• Реновация школ в нашем округе обойдется в 23 млн долларов.

Разумеется, я не стал разделять разряды в первом случае, чтобы число было сложнее прочесть (и я попал в точку, не правда ли?). Но, даже если проставить пробелы, фраза «Пентагон требует дополнительные 19 000 000 000 долларов» сложнее для восприятия, чем «Пентагон требует дополнительные 19 млрд долларов». Иногда удобнее использовать слова вместо чисел.

Мнимое преимущество позиционной системы счисления[29]29
  Позиционная система счисления – это такая система счисления, в которой значение каждого символа в записи числа зависит от его позиции (разряда). – Прим. пер.


[Закрыть] – это то, что в ней проще производить вычисления. Но давайте задумаемся о том, сколько сил уходит на перемножение двух чисел. Во-первых, нам необходимо запоминать дополнительные математические данные. К тому же мы обязаны помнить таблицу умножения. Во-вторых, мы проделываем многоуровневую процедуру: сортируем числа по разрядам, умножаем по соответствующему правилу, получаем промежуточные данные, складываем.

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

Единичная система счисления

Простейший способ записи чисел – единичная система счисления: мы просто записываем столько же символов (будем использовать цифру 1), сколько единиц в интересующем нас числе. Например, число 3 окажется трехзначным: 111. Сложение и умножение становятся исключительно простыми. Чтобы сложить 3 и 5, мы просто запишем два числа, 111 и 11111, друг за другом (без пробела) – и вот он, ответ: 11111111. Умножать тоже просто. Мы запишем одно число вертикально, а другое горизонтально и получим следующую таблицу:

Затем мы заполним таблицу, поставив единичку в каждом столбце и в каждой колонке:

Наконец, мы выпишем все единички в ряд и получим ответ: 111111111111111. Складывать и перемножать числа в единичной системе счисления существенно проще, чем десятичные или римские числа[30]30
  Предлагаю вам самостоятельно найти алгоритмы для вычитания и деления.


[Закрыть].

Разумеется, такая простота вычислений дается ценой титанических затрат внимания и времени. Никому не захочется прибегать к этому методу, чтобы перемножить 47 и 924.

Компромисс

Числа, записанные в двоичной системе счисления[31]31
  Также говорят: система счисления с основанием 2.


[Закрыть], не так привычны нам, как десятичные или римские, но с ними проще делать вычисления. Вот почему в компьютерах используется именно двоичная система. Чтобы разобраться, как она устроена, нам нужно припомнить особенности десятичной системы.

Для записи чисел в десятичной системе счисления используют десять символов, располагаемых в разных комбинациях в ряд по горизонтали. Значение символа зависит от его места в ряду. 29 и 92 означают разные числа, потому что 2 и 9 занимают разные позиции. 29 означает «два десятка и девять единиц». 5804 означает «пять тысяч, восемь сотен, ни одного десятка и четыре единицы». Позиция цифры в десятичном числе означает, на какую степень десяти[32]32
  Напомним, что показатель степени означает, сколько раз мы перемножаем основание: например, 10³ = 10 × 10 × 10. Естественно, 10¹ = 10. По договоренности, 10⁰ = 1. Это логично, так как каждая следующая степень десяти в десять раз больше предыдущей.


[Закрыть] мы ее умножаем. Разряды растут справа налево: единицы, десятки, сотни, тысячи, десятки тысяч и т. д. Иными словами, запись 5804 означает:

5 × 10³ + 8 × 10² + 0 × 10¹ + 4 × 10⁰.

Чем больше символов в десятичном числе, тем труднее его прочесть. Обычно каждый четвертый разряд отделяют пробелом или запятой[33]33
  В англоязычных странах в качестве разделителя разрядов используется запятая, в России – неразрывный пробел, который ставится только в числах с пятью и более разрядами. – Прим. ред.


[Закрыть].

Двоичная система устроена схожим образом, просто позиция в записи означает, на какую степень двух (а не десяти) мы должны умножить эту конкретную цифру.

В двоичной системе счисления используются всего два символа: 0 и 1. Разряды здесь тоже растут справа налево, обозначая количество единиц, двоек, четверок, восьмерок и т. д. Например, в двоичной записи 10110 означает:

1 × 2⁴ + 0 × 2³ + 1 × 2² + 1 × 2¹ + 0 × 2⁰ = 16 + 4 + 2 = 22.

Проверьте, насколько вы ориентируетесь в новой теме: чему равно число 42 в двоичной системе и чему равно число 11011₂ в десятичной[34]34
  Чтобы отличить запись в двоичной системе от записи в десятичной, мы будем ставить нижний индекс: 1101₂ или 1101₁₀.


[Закрыть]? Ответы – в конце главы.

Вычисления

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

Заметьте, что в таблице умножения 10 означает число два.

Сложение двоичных чисел устроено так же, как в десятичной системе. Например, нам нужно найти сумму 10100₂ и 1110₂. Расположим эти числа друг над другом:

Дальше нужно двигаться справа налево, складывая цифры в каждом столбце и при необходимости перемещая единицу на столбец влево. В нашем случае мы сложим два нуля и получим ноль:

Дальше идет столбец двоек. Мы складываем 1 и 0 (переносить ничего не требуется):

Дальше – столбец четверок. Мы складываем 1 и 1, получаем 10, пишем 0, держим 1 в уме и переносим на столбец влево:

Следующий столбец – восьмерки. Складываем 1 и 0 и 1, получаем 10, пишем 0 и держим 1 в уме:

Заканчиваем на столбце, означающем, сколько раз в числе встречается 16. Сложение дает 10, мы пишем 0 в текущем столбце и 1 в столбце с разрядом 32:

Мы обнаружили, что 10100 + 1110 = 100010.

Переведем это на язык десятичных чисел:

10100₂ = 20, 1110₂ = 14, 100010₂ = 34.

Разумеется, 20 + 14 = 34.

Умножение в двоичной системе проще, чем в десятичной. Достаточно усвоить два принципа: сложение двоичных чисел (мы в нем только что разобрались) и умножение на степени двойки.

Умножение числа на 10 в десятичной системе не представляет сложности: мы просто добавляем цифру 0 справа: 23 × 10 = 230. Точно так же выглядит умножение на 2 в двоичной системе: 1101 × 10 = 11010. В случае десятичных чисел это очевидно, в случае двоичных 1101 означает:

1 × 8 + 1 × 4 + 0 × 2 + 1 × 1.

Умножение на 2:

1 × 16 + 1 × 8 + 0 × 4 + 1 × 2 + 0 × 1.

Лишний ноль на конце дает 11010.

Умножение на 4, 8 и другие степени двойки тоже просто: например, умножение на 8₁₀ (1000₂) равнозначно приращению трех нулей с правой стороны числа.

Итак, умножение превращается в игру «перемести-и-добавь-цифры». Проиллюстрируем это на примере умножения 11010 на 1011. Для начала запишем второе число так:

1011 = 1000 + 10 + 1.

Умножение на 11010 можно представить так:

11010 × 1011 = 11010 × (1000 + 10 + 1) = 11010 × 1000 + 11010 × 10 + 11010 × 1 = 11010000 + 110100 + 11010.

Удобнее умножать в столбик:

А вот и ответ:

Давайте переведем числа в десятичные, чтобы удостовериться, что все правильно:

11010₂ = 16 + 8 + 2 = 26;

1011₂ = 8 + 2 + 1 = 11;

100011110₂ = 256 + 16 + 8 + 4 + 2 = 286.

Мы не ошиблись: 26 × 11 = 286.

Дроби

В десятичной системе мы можем записывать не только целые числа. Если поставить в конце запятую[35]35
  В английской традиции записи целую часть десятичного числа от дробной отделяет точка, в русской – запятая. – Прим. ред.


[Закрыть], мы получим новые места для цифр: по мере движения вправо степени десяти будут все меньше. Например, 34,27 – это компактный способ записи такого выражения:

Двоичная система тоже позволяет записывать дробные значения. Каждую следующую цифру после запятой[36]36
  В случае с двоичной системой неправильно говорить «десятичная запятая», лучше называть ее двоичной запятой, или запятой в позиционном представлении числа.


[Закрыть] мы умножаем на предыдущую степень двойки. Например, 101,011₂ означает:

Непривычный способ записать одну вторую: 0,1₂!

Есть и другие системы счисления, помимо десятичной, единичной и двоичной[37]37
  Программисты нередко пользуются шестнадцатеричной системой счисления. В десятичной системе 10 цифр (от 0 до 9), в шестнадцатеричной нам нужно 16 разных символов, поэтому числа от 10 до 15 обозначают с помощью букв от A до F.


[Закрыть]. В третичной системе мы пользуемся цифрами 0, 1 и 2, здесь все строится на степенях тройки. Скажем, 1102₃ означает:

1 × 27 + 1 × 9 + 0 × 3 + 2 × 1 = 38.

В дробях первая позиция справа от запятой означает умножение на одну третью, вторая позиция – на одну девятую и т. д.:

Ответ на задачу в разделе «Компромисс»

Если представить 42 в виде суммы степеней двойки, мы увидим, что это 101010₂. А число 11011₂ можно представить как 16 + 8 + 2 + 1 = 27.

Глава 3
0,99999999999…

Безусловно, простейший способ записать число один – это цифра 1. Но вы можете столкнуться с тем фактом, что уходящая в бесконечность десятичная дробь 0,999999… представляет собой другой способ записи того же числа. В главе 3 мы присмотримся к этому обстоятельству повнимательнее.

Что означают десятичные числа?

Привычная нам десятичная система счисления удобна и работает отменно, почти без перебоев. Она хорошо подходит для записи целых чисел. 235 – это компактный способ сказать «две сотни, три десятка и пять единиц». Или, на языке математики:

235 = 2 × 100 + 3 × 10 + 5 × 1.

Для некоторых дробных величин десятичная система счисления также чрезвычайно эффективна. Возьмем число 3/4. В десятичной системе его можно записать так: 0,75. Эта запись означает:

Десятичная дробь 0,75 в точности равна 3/4.

Тем не менее если мы предпримем попытку записать 2/7 в виде десятичной дроби, то потерпим фиаско. Если мы попробуем разделить два на семь с помощью калькулятора, то получим неприглядное 0,28571429, причем это будет лишь приближенное значение, не равное в точности 2/7.

Такие числа, как 3/8, могут быть представлены в виде десятичной дроби, потому что знаменатель в них легко представить в виде одной из степеней десятки: 3/8 = 375/1000. Но нельзя найти целое число A, для которого выполнялось бы условие:

так как это подразумевает 2 × 10ⁿ = 7 × A. Ни одно целое число A не подходит в качестве решения уравнения, потому что левая сторона не делится на 7, а правая сторона делится. Представить 2/7 в качестве десятичной дроби невозможно. Если только не…

Десятичные дроби с бесконечным числом символов

Идея десятичной дроби с бесконечным числом символов содержит в себе один подвох, и сейчас мы выясним, какой именно. Вернемся к началу главы: что означает 0,99999… и почему оно равно 1?

Для начала давайте представим 0,999999… не как одно число, а как ряд чисел, где каждое следующее – это предыдущее с приделанной справа цифрой 9. Вот как выглядит такой ряд:

0,9 0,99 0,999 0,9999 … (*)

и так далее ad infinitum[38]38
  До бесконечности (лат.). – Прим. пер.


[Закрыть]. Ясно, что элементы ряда (*) постоянно возрастают. Каждый следующий элемент пусть ненамного, но больше предыдущего.

Докажем два факта:

1. Все элементы возрастающего ряда (*) меньше 1.

2. Тем не менее для любого числа x, которое меньше 1, рано или поздно отыщется элемент ряда (*), превышающий x.

Представим элементы ряда (*) в виде обыкновенных дробей:

Есть компактный способ записать эти дроби. Знаменатели представляют собой степени десяти: 10¹, 10², 10³ и т. д. Каждый числитель на единицу меньше соответствующего ему знаменателя. Перепишем ряд снова:

Очевидно, что n-ный элемент ряда будет выглядеть так:

Легко убедиться, что все члены ряда (*) меньше 1, потому что числитель всякий раз оказывается меньше знаменателя.

Теперь докажем второе утверждение: если число x меньше 1, рано или поздно найдется элемент ряда (*), превышающий x.

Так как x меньше 1, разность (1 – x) положительна. Даже если x невероятно близок к единице, разница между ними будет мизерная, но положительная. Умножим (1 – x) на одну из степеней десяти:

10ⁿ × (1 – x).

Так как разность (1 – x) положительна, это произведение будет больше 1, если 10ⁿ достаточно велико[39]39
  Строго говоря, это утверждение тоже надо доказать. – Прим. науч. ред.


[Закрыть]:

10ⁿ × (1 – x) > 1.

Раскроем скобки:

10ⁿ – 10ⁿx > 1,

перенесем 1 в левую часть, а 10ⁿx в правую:

10ⁿ – 1 > 10ⁿx,

поделим обе части на 10ⁿ:

Что мы выяснили? С одной стороны, все элементы интересующего нас возрастающего ряда меньше 1. С другой стороны, какое бы число x меньше единицы мы ни взяли, рано или поздно возникнет элемент ряда, превышающий x (а последующие будут нарастать и все больше удаляться от x).

Наш ряд неуклонно приближается к 1. Математики говорят, что этот ряд стремится к 1. Или, что то же самое, 1 представляет собой предел ряда.

Значение десятичной дроби с конечным числом символов – это сумма определенного количества десятых, сотых, тысячных и т. д. Например:

К сожалению, язык десятичных дробей с конечным числом символов слишком скуден, чтобы выразить, например, 2/7. Поэтому нам необходимо расширить лексикон.

Значение десятичной дроби с бесконечным числом символов равно пределу ряда, где на каждой ступени элемент прирастает на одну цифру. Это сложно, однако дает нам возможность выражать все числа, используя десятичную систему счисления.

Уходим в беспредел!

Нужно приложить определенные усилия, чтобы увидеть в бесконечной десятичной дроби предел ряда. Попробуем посмотреть проще.

Вернемся к знакомому нам 0,999999… Пусть:

X = 0,999999… (A)

Умножим обе части равенства на 10:

10X = 9,999999… (B)

Вычтем (A) из (B):

9X = 9,000000…

Теперь поделим обе части на 9 и убедимся, что X = 1. Готово! Все оказалось просто.

Этот фокус можно повторить для любой периодической десятичной дроби. Например:

Y = 0,27272727… (C)

Умножим обе части на 100 (чтобы цифры встали в строй):

100Y = 27,27272727… – (D)

и вычтем (C) из (D):

99Y = 27,000000…

Таким образом, Y = 27/99 = 3/11.

Вот видите[40]40
  Проверьте, насколько хорошо вы усвоили материал, и выразите 0,123123123123… в виде обыкновенной дроби. Ответ в конце главы.


[Закрыть]! Зачем утруждать себя «сходимостями» и «пределами»? Но с бесконечными последовательностями нужно быть осторожнее. Представим себе сумму:

Z = 1 + 2 + 4 + 8 + 16 + 32 + … (E)

Умножим обе части равенства на 2:

2Z = 2 + 4 + 8 + 16 + 32 + … – (F)

и привычно вычтем (E) из (F):

– Z = 1.

Стало быть, Z = –1? Что за абсурд?

Где мы допустили оплошность? Мы ушли в беспредел. Алгоритм, позволяющий установить значение 0,9999999… и 0,2727272727…, дал сбой, когда мы взялись за ряд 1 + 2 + 4 + 8 + 16… Во всех трех случаях речь шла о бесконечной последовательности. В чем разница? Ответ: в сходимости. Не понимая толком, что такое сходимость ряда, мы запросто придем к выводу, что сумма положительных чисел может быть отрицательным числом. Операции с выражениями (A) и (B), а также (C) и (D) математически корректны, потому что мы имеем дело со сходящимися последовательностями.

Глава 4
√2

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

Рациональные числа

Целые числа прекрасно ладят с тремя простейшими арифметическими действиями – со сложением, вычитанием и умножением. Мы производим эти операции над двумя целыми числами и получаем целое же число. А вот деление одного целого числа на другое[41]41
  Так как делить на ноль нельзя, я имею в виду такие операции, как 7/5.


[Закрыть] может привести к дробному результату.

Числа, представляющие собой результат деления целого числа на целое, называют рациональными[42]42
  Термин «рациональные числа» происходит от латинского слова ratio, но вовсе не потому, что они, в отличие от прочих, обладают здравым смыслом.


[Закрыть]. Например, 1,5 – это рациональное число, потому что равно 3/2.

Целое число 3 рациональное, потому что 3 = 3/1 (а еще 6/2, 12/4 и т. д.). Все целые числа – рациональные.

Целые числа ладят с тремя арифметическими действиями, а рациональные числа – со всеми четырьмя. Сумма, разность, произведение и частное рациональных чисел всегда будут рациональным числом (с привычной оговоркой о неправомерности деления на ноль).

Рациональные числа пригодны для описания повседневной жизни. Величины, которые мы измеряем, – вес, интенсивность звука, расстояние, цена, температура, время, численность населения, радиочастоты – выражаются рациональными числами.

Но если рациональные числа удобны для работы и над ними можно осуществлять арифметические операции, зачем нам другие числа?

Можно задаться более фундаментальным вопросом: существуют ли другие числа?

Диагональ квадрата

Каково расстояние между противоположными вершинами квадрата? Позже, в главе 14, мы обсудим решение этой задачи. Сейчас же достаточно знать, что длина диагонали квадрата 1 × 1 равна √2

Если умножить число √2 само на себя (другими словами, возвести в квадрат), мы получим 2. Посчитайте приблизительное значение √2 на калькуляторе. А теперь давайте посмотрим, можно ли приблизиться к этому числу с помощью ручки и бумаги.

Начнем с того, что, если возвести в квадрат 0, получится 0, а если возвести в квадрат 1, получится 1. Наша цель 2, а найденные числа меньше. С другой стороны, если возвести в квадрат 2, мы получим 4, а если возвести в квадрат 3, получим 9. Это больше, чем нам нужно.

1² – слишком ма́ло, 2² – слишком много. Попробуем найти величину между 1 и 2, перемещаясь с шагом 0,1, как показано в таблице.

Легко заметить: 1,4 слишком мало для квадратного корня из двух, а 1,5 – слишком велико. Следовательно, √2 лежит между этими двумя величинами.

Продолжим в том же духе. Будем возводить в квадрат числа между 1,4 и 1,5, двигаясь с шагом 0,01. Мы обнаружим, что 1,41² = 1,9881, а 1,42² = 2,0164. Из этого можно сделать умозаключение, что

Мы можем двигаться таким образом все дальше и дальше, приближаясь к √2

Рано или поздно мы либо успокоимся (достигнув числа, фантастически близкого к либо почувствуем отчаяние (увидев, что никогда не сможем точно вычислить √2

Но что означает это «точно»?

За границами рационального

Разумный способ определить точное значение числа – представить его в виде рационального числа, то есть отношения двух целых чисел. Если бы мы сумели представить √2 в виде дроби где a и b – целые числа, мы бы нашли его точное значение.

Увы, но такое невозможно. Однако это нужно доказать.

Теорема. √2 не является рациональным числом.

Будем идти от противного, как и в главе 1, где мы подсчитывали количество простых чисел. Предположим, что √2 – рациональное число. Если это допущение приведет к абсурдным выводам, значит, оно несостоятельно.

Итак, приступим. Если √2 – рациональное число, его можно выразить в виде отношения двух целых чисел:

Возведем обе части тождества в квадрат:

Раскроем скобки:

Таким образом:

или:

2b² = a². (С)

Если a – целое число, мы можем разложить его на простые множители, причем (согласно основной теореме арифметики) одним-единственным способом:

a = p₁ × p₂ × … × p_n.

Проделаем аналогичную процедуру с b:

b = q₁ × q₂ × … × q_m.

Следовательно, левую часть равенства (С) можно представить в таком виде:

2b² = 2 × (q₁ × q₂ × … × q_m)² = 2 × (q₁ × q₁) × (q₂ × q₂) × … × (q_m × q_m).

Несложно заметить, что 2b² раскладывается на нечетное число простых множителей.

Аналогично поступаем с правой частью (С):

a² = (p₁ × p₂ × … × p_n) ² = (p₁ × p₁) × (p₂ × p₂) × … × (p_n × p_n).

В отличие от 2b², выражение a² раскладывается на четное число простых множителей.

Подытожим. В соответствии с нашим предположением 2b² = a². Это означает, что некоторое число одновременно можно разложить на четное и нечетное количество простых множителей. Но это противоречит основной теореме арифметики.

Мы пришли к невозможному выводу. Таким образом, наша изначальная посылка была ошибочна. Следовательно, √2 не является рациональным числом.

Такие числа, как √2 называют иррациональными. Рациональные числа хороши для операций с физическими величинами[43]43
  Не со всеми: есть физические величины, про которые нет оснований полагать, что отношения между ними выражаются в рациональных числах. Впрочем, как следует из сказанного выше, можно добиться сколь угодно точного приближения рациональными числами. – Прим. науч. ред.


[Закрыть], но их недостаточно для всех математических величин. Длина диагонали квадрата 1 × 1 – иррациональное число.

Конструктивные числа

Начав с числа 1 и шаг за шагом проделывая операции сложения, вычитания и умножения, мы можем получить любое целое число, но и только. Если мы добавим операцию деления, нам откроются все рациональные числа, но ими же мы и будем ограничены.

Если мы введем операцию извлечения квадратного корня[44]44
  Здесь мы рассматриваем исключительно квадратные корни из неотрицательных чисел. В главе 5 мы увидим, что в математике есть область, где можно извлекать квадратный корень из отрицательного числа.


[Закрыть], то получим числа, которые не являются отношением целых чисел. Например:

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

Разумеется, возникает вопрос: все ли числа конструктивные?

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

Складывать и вычитать отрезки просто. Пусть у нас есть отрезки длиной a и b. С помощью линейки мы продлеваем первый отрезок. Ставим иглу циркуля в начало второго отрезка, а острие карандаша на другой ножке циркуля – в конец отрезка. После этого мы перемещаем иглу в конец первого отрезка и отмечаем точку на продленной линии. Так мы находим сумму двух отрезков. Что касается вычитания, оно будет означать не приращение, а укорочение отрезков.

Дальше дело пойдет несколько сложнее, но мы вполне способны умножать, делить и даже извлекать квадратные корни из длин отрезков с помощью линейки без делений и циркуля.

Да, это так: с помощью двух простейших инструментов мы можем найти длины, равные всем положительным конструктивным числам!

Было время, когда греки думали, что все числа рациональные, но пифагорейцы доказали, что это не так.

Однако грекам было непросто расстаться с верой в связь арифметики и геометрии. В основе этой веры лежали представления об эстетике. Неужели не все числа можно выразить с помощью линейки без делений и циркуля?

Эта вера подкреплялась решениями двух из трех знаменитых древнегреческих геометрических задач. Наиболее известна задача о трисекции угла: с помощью линейки без делений и циркуля нужно поделить заданный угол на три равных угла[45]45
  Задача о бисекции угла существенно проще. Нет ничего сложного в том, чтобы с помощью циркуля и линейки прочертить луч, разделяющий заданный угол на два равных между собой угла.


[Закрыть].

Менее известны две другие головоломки:

• Удвоение куба. Необходимо найти длину ребра куба, чей объем в два раза больше заданного. Если длина ребра первого куба – единица, это равносильно построению отрезка длиной

• Квадратура круга. Необходимо построить квадрат, чья площадь равна площади заданного круга. Если радиус круга равен единице, его площадь равна π. Тогда сторона квадрата будет равна

Понадобилось две тысячи лет, чтобы понять: эти задачи неразрешимы[46]46
  Пьер Ванцель строго доказал, что задачи об удвоении куба и трисекции угла неразрешимы, в 1837 году.


[Закрыть]. Ни ни не являются конструктивными числами[47]47
  Неразрешимость задачи о квадратуре круга стала ясна в 1882 году, когда Фердинанд фон Линдеман доказал, что число π трансцендентно. – Прим. пер.


[Закрыть]. Решая проблему трисекции угла, мы сталкиваемся с тем фактом, что некоторая величина (косинус 20°) не является конструктивным числом.

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

Музыкальная гармония

Если музыканты перед концертом не настроили инструменты, возникает акустический диссонанс: музыка становится неблагозвучной.

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

Этот вопрос волновал еще древних греков. Они выяснили, что, если акустические частоты соотносятся как малые целые числа (например, 2 и 3), сочетание нот ласкает слух. Так был открыт первый музыкальный строй (по легенде, его создал Пифагор[48]48
  Пифагор Самосский (VI–V вв. до н. э.) – древнегреческий философ, математик, мистик, основатель религиозного движения пифагорейцев. – Прим. пер.


[Закрыть]). Подбирая частоты для нот, важно выполнить главное требование: частоты нот, находящихся на противоположных концах октавы, должны соотноситься примерно как 2:1. Ради гармоничных звуков древние греки подбирали ноты так, чтобы парное соотношение частот до и фа, а также до и соль выражалось малыми целыми числами. В пифагорейском варианте соотношение между частотами соседних нот было равно 9/8 для целого тона (например, между до и ре) и 256/243 для полутона (например, между ми и фа).

Вот весь пифагоров строй[49]49
  Число 9/8 над стрелкой означает, что частота ноты справа в 9/8 раза больше частоты ноты слева.


[Закрыть]:

Из этого соотношения можно посчитать соотношение, скажем, между частотами нот до и фа. Мы получим частоту фа, если умножим частоту до на

Акустические частоты, соотносящиеся как 4:3, прекрасно звучат вместе.

Мы можем визуализировать звуковые волны, возникающие, когда до и фа звучат вместе. Это будет выглядеть примерно так:

А частота ноты ля окажется немножко выше, звуковая волна будет выглядеть так:

Разница, заметная для глаза, заметна также и для слуха; вы видите диссонанс.

Недостаток пифагорова строя в том, что широко распространенное мажорное трезвучие до мажор – до-ми-соль – звучит как диссонанс; соотношение частот достаточно сложное.

Спустя много веков были найдены другие варианты. Например, так называемый чистый строй, или натуральный строй[50]50
  Подобран венецианскими композиторами и теоретиками музыки в XVI веке. – Прим. пер.


[Закрыть], выглядит так:

В этом варианте частоты до, ми и си прекрасным образом соотносятся как 4:5:6. Но полный тон от до до ре звучит иначе, чем другой полный тон от ре до ми.

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

Исправить изъян можно, если создать музыкальный строй, действующий одинаково хорошо во всех тональностях. Это накладывает два условия:

1. Частоты нот на противоположных концах октавы должны соотноситься как 2:1;

2. Если ноты отделены полутоном, соотношение их частот должно быть таким же, как у остальных полутонов октавы (например, соотношение частот до и ми-диез равно соотношению частот до-диез и ре). Всего в октаве двенадцать полутонов: до, до-диез, ре, ми, ми-диез, фа, фа-диез, соль, соль-диез, ля, ля-диез и си.

Если соотношение частот любых двух соседних нот равно r (условие 2), а соотношение частот двенадцатой и первой ноты равно 2 (условие 1), то r¹² = 2. Следовательно,

Если настроить музыкальные инструменты таким образом, чтобы соотношение частот соседних нот в октаве было равно не придется перенастраиваться при переходе в другую тональность. Этот музыкальный строй называют равномерно темперированным[51]51
  Равномерно темперированный строй господствует в европейской музыке с XVIII века, однако его теоретическое обоснование встречается уже в работах XVI века, причем не только в Европе, но и в Китае. – Прим. пер.


[Закрыть], и сегодня им пользуются все профессиональные музыканты.

К сожалению, число иррационально[52]52
  Доказательство похоже на доказательство того, что значение √2 иррационально. Попробуйте найти его самостоятельно.


[Закрыть]. Иными словами, соотношение частот двенадцати нот в равномерно темперированном строе (за исключением начала и конца октавы) не может быть выражено через соотношение целых чисел. Соотношение частот до и соль в таком случае равно не 3:2, а примерно 1,4983 (число принято округлять до 1,5).

Как это звучит? Сейчас почти все музыкальные инструменты настраивают по равномерно темперированному строю, и они ласкают наш слух. Но что мы теряем?

Вот как выглядит звуковая волна для трезвучия до мажор. В первом варианте частоты нот соотносятся как 4:5:6, во втором подобраны в соответствии с равномерно темперированным строем. Первый вариант выглядит (и звучит!) гораздо гармоничнее.

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

Вокальные ансамбли без инструментального сопровождения (например, «парикмахерские» квартеты[53]53
  Мужские вокальные ансамбли в США, исполняющие популярную музыку а капелла. – Прим. пер.


[Закрыть]) не нуждаются в равномерно темперированном строе и берут ноты, соотношение частот которых можно выразить целыми числами. И мы слышим чудесные хорошо резонирующие звуки.