Число как объект изучения (Теория чисел)
Видео и статья на тему «Математика за 20 уроков»
Раздел 1. Что можно изучать в числах? (00:00)
Сегодня мы опять поговорим о числах, но теперь сами числа будут являться предметом изучения. Мы ввели числа как инструмент для размышления о количествах. Все, что делает человек, рано или поздно становится объектом его изучения, в том числе и то, что он сам создал. Например: есть теория игр, в ней, в частности, изучается игра в шахматы, а все знают, что эта игра придумана человеком. Еще один пример: лингвистика – изучение языка, который также придуман человеком. Поэтому в каком-то смысле число существует и его можно изучать.
Теория чисел – самая старая часть математики, она зародилась в Древней Греции. Древнегреческие философы полагали, что «все есть число». Они занимались изучением самого числа, именно тогда появились первые теоремы, первые постановки задач.
Машины и механизмы
Другая область деятельности, где тоже порождения человека стали предметом изучения, – это теория машин и механизмов, большой вклад в которую внес наш соотечественник Чебышев. Он изобрел первого робота для выставки во Франции (Рис. 1). Элементарные машины и механизмы проходят еще в школе (Рис. 2). Теория машин и механизмов как наука была разработана в XIX веке, хотя этим занимались и Архимед, и Леонардо да Винчи.
Рис. 1. Стопоходящая машина
Рис. 2. Элементарные машины и механизмы
Что же можно изучать в числах? Когда мы берем какой-то механизм, он состоит из деталей, а мы эти детали изучаем. Например: часовщик должен хорошо знать, из чего состоят различные виды часов, как работают шестеренки и т.д. То же самое можно сказать и про число. Если рассматривать число как сумму единиц, тогда все, что можно изучать, – это сравнение чисел (больше/меньше). А вот если рассматривать число как произведение некоторых множителей, то уже возникают интересные вещи, которые составляют основу теории чисел.
Так как 4 – это 2 умножить на 2, то это число, которое, кроме единицы и самого себя, делится на еще какое-то число. Такие числа называют составными. Примеры:
4 = 2 ∙ 2 = 4 ∙ 1
6 = 3 ∙ 2 = 6 ∙ 1
8 = 4 ∙ 2 = 8 ∙ 1
Есть и другие числа, простые. Это те числа, которые делятся только на единицу и на себя. Составные числа составлены из простых чисел, как дом составлен из кирпичей. Примеры простых чисел: 2, 3, 5, 7, 11… Кажется, что чем больше число, тем более вероятно, что оно будет составным. Поэтому логично предположить, что рано или поздно наберется такое количество простых чисел, что любое число можно будет составить из них. Но эти рассуждения неверны, и еще Евклид доказал, что простых чисел бесконечно много.
Так как 4 – это 2 умножить на 2, то это число, которое, кроме единицы и самого себя, делится на еще какое-то число. Такие числа называют составными. Примеры:
4 = 2 ∙ 2 = 4 ∙ 1
6 = 3 ∙ 2 = 6 ∙ 1
8 = 4 ∙ 2 = 8 ∙ 1
Есть и другие числа, простые. Это те числа, которые делятся только на единицу и на себя. Составные числа составлены из простых чисел, как дом составлен из кирпичей. Примеры простых чисел: 2, 3, 5, 7, 11… Кажется, что чем больше число, тем более вероятно, что оно будет составным. Поэтому логично предположить, что рано или поздно наберется такое количество простых чисел, что любое число можно будет составить из них. Но эти рассуждения неверны, и еще Евклид доказал, что простых чисел бесконечно много.
Доказательство
Будем использовать метод от противного: предположим, что некоторое утверждение неверно, исходя из этого получим логическое противоречие. Тогда исходное утверждение будет верно.
Предположим, что простых чисел конечное число: p₁, p₂,…, pN. Рассмотрим число A = p₁ ∙ p₂ ∙...∙pN + 1. Данное число не будет делиться ни на одно из этих простых чисел, но это значит, что оно само простое. Значит, наше предположение было неверно, и простых чисел бесконечное множество.
Данное доказательство не помогает нам найти формулу для нахождения простых чисел, более того, такой простой формулы и не существует.
Предположим, что простых чисел конечное число: p₁, p₂,…, pN. Рассмотрим число A = p₁ ∙ p₂ ∙...∙pN + 1. Данное число не будет делиться ни на одно из этих простых чисел, но это значит, что оно само простое. Значит, наше предположение было неверно, и простых чисел бесконечное множество.
Данное доказательство не помогает нам найти формулу для нахождения простых чисел, более того, такой простой формулы и не существует.
Значительный вклад в изучение чисел сделал наш соотечественник Чебышев. Евклид доказал, что количество простых чисел бесконечно, но как часто они будут встречаться? На этот вопрос и ответил Чебышев, то есть он нашел плотность распределения простых чисел. Например, в диапазоне от 0 до 10²³ всего 1 925 320 391 606 803 968 923 простых числа.
Простые числа-близнецы
Рассмотрим простые числа-близнецы, то есть простые числа, которые идут через два числа (через одно идут только простые числа 2 и 3). Например, 11 и 13 или 101 и 103. Кажется, что чем дальше мы продвигаемся по числовому ряду, тем меньше должно быть таких пар чисел. Но это не так: есть очень большие простые числа, которые также близки друг к другу: например, 3756801695685 ∙ 2⁶⁶⁶⁶⁶⁹ - 1 и 3756801695685 ∙ 2⁶⁶⁶⁶⁶⁹ + 1.
Это еще один любопытный факт о плотности распределения простых чисел. Конечно, любопытен он в основном для тех, кто погружен в математику. В этом отличие математики от других наук. Если рассмотреть, например, биологию, то в ней понятно, чем занимаются ученые – изучают живые организмы. А математика по мере своего развития занимается вещами, которые все дальше и дальше уходят от реальной жизни. Это связано с тем, что объектами изучения математики являются порождения разума человека, то есть математика изучает инструмент мышления человека.
Это еще один любопытный факт о плотности распределения простых чисел. Конечно, любопытен он в основном для тех, кто погружен в математику. В этом отличие математики от других наук. Если рассмотреть, например, биологию, то в ней понятно, чем занимаются ученые – изучают живые организмы. А математика по мере своего развития занимается вещами, которые все дальше и дальше уходят от реальной жизни. Это связано с тем, что объектами изучения математики являются порождения разума человека, то есть математика изучает инструмент мышления человека.
Одним из самых простых применений теории чисел являются пифагоровы тройки. То есть это три числа, сумма квадратов двух из которых, равна квадрату третьего числа (Рис. 3).
Рис. 3. Пифагоровы тройки
Берутся они из теоремы Пифагора (сумма квадратов катетов равна квадрату гипотенузы). Но верна и обратная теорема. Если для трех чисел верно такое равенство, то треугольник, длины сторон которого будут равны этим числам, будет прямоугольным.
Поэтому для получения прямого угла в Древнем Египте брали веревку, делили ее на 12 равных частей, тогда если взять 3 части и 4 части, то угол, который они образуют, будет прямым (Рис. 4).
Рис. 4. Построение прямого угла
Это один из примеров практического применения теории чисел.
Если углубиться в развитие теории чисел, то одна из величайших проблем математики – это теорема Ферма. Для обывателя ее формулировка не сильно отличается от теоремы Пифагора. В ней рассматривается похожее уравнение, но не для квадратов, а кубов, четвертых степеней, пятых степеней и т.д. для любого показателя степени.
Если углубиться в развитие теории чисел, то одна из величайших проблем математики – это теорема Ферма. Для обывателя ее формулировка не сильно отличается от теоремы Пифагора. В ней рассматривается похожее уравнение, но не для квадратов, а кубов, четвертых степеней, пятых степеней и т.д. для любого показателя степени.
Раздел 2. Великая теорема Ферма (08:44)
Для любого натурального числа n > 2 уравнение aⁿ + bⁿ = cⁿ не имеет решений в целых ненулевых числах a, b, c.
Формулировка этой теоремы достаточно проста, поэтому она стала притягательной для тех, кто хотел ее доказать. Лишь относительно недавно эта теорема была доказана. Пока эта затратная по усилиям теорема сама по себе оказалась не слишком полезной. Но для доказательства теоремы были разработаны такие методы, которые с успехом применяются в физике и других науках.
Можно задаться вопросом: для чего это все нужно? Но на самом деле так часто бывает: то, что делается в свободном творчестве, затем находит применение для решения практических задач. Вот цитата из стихотворения Пушкина:
Можно задаться вопросом: для чего это все нужно? Но на самом деле так часто бывает: то, что делается в свободном творчестве, затем находит применение для решения практических задач. Вот цитата из стихотворения Пушкина:
История показывает, что поэт был прав. Возьмем, например, компьютер. Когда он начал применяться, все говорили, что он нужен только для решения инженерных задач (его даже называли ЭВМ – электронно-вычислительная машина). А сейчас компьютеры используют для решения практически любых задач. А автомобили всего лишь 100 лет назад считали грязной и ненужной игрушкой и т.д.
Можно привести много примеров, когда все человечество заблуждалось: химия зарождалась как наука о поиске философского камня, алхимия. Пытались сделать из куска железа золото, сейчас мы знаем, что это невозможно. Но попробуйте сейчас представить без химии нашу жизнь: что будет, если убрать, например, всю синтетику.
Вернёмся к теории чисел. Еще одним естественным вопросом, кроме возможности разложения числа на множители, является вопрос: как быстро число разложить на множители. На уроках вы будете изучать признаки делимости. Они позволяют быстро сказать, делится или нет число, например, на 3. Зачем это нужно? Есть практические задачи. Например, у нас есть большое количество монет, мы хотим узнать, сможем ли мы их поровну разделить между тремя людьми.
Можно привести много примеров, когда все человечество заблуждалось: химия зарождалась как наука о поиске философского камня, алхимия. Пытались сделать из куска железа золото, сейчас мы знаем, что это невозможно. Но попробуйте сейчас представить без химии нашу жизнь: что будет, если убрать, например, всю синтетику.
Вернёмся к теории чисел. Еще одним естественным вопросом, кроме возможности разложения числа на множители, является вопрос: как быстро число разложить на множители. На уроках вы будете изучать признаки делимости. Они позволяют быстро сказать, делится или нет число, например, на 3. Зачем это нужно? Есть практические задачи. Например, у нас есть большое количество монет, мы хотим узнать, сможем ли мы их поровну разделить между тремя людьми.
Когда перед нами большое число, например, 13745980167, то кажется, что сложно понять, на что оно делится. Но, посчитав сумму его цифр (1 + 3 + 7 + 4 + 5 + 9 + 8 + 0 + 1 + 6 + 7 = 51), можно сразу сказать, что оно делится на 3 (признак делимости на 3: число делится на 3 тогда и только тогда, когда сумма цифр числа делится на 3).
Этот же вопрос можно рассмотреть с другой стороны. Предположим, вы пришли в магазин. У вас только 10-рублевые монеты, а у продавщицы – 5-рублевые. В таком случае она никак не сможет дать вам сдачу 1 рубль. А вот если бы у вас были 5-рублевые, а у нее – 2-рублевые, то это было бы возможно, так как числа 5 и 2 являются взаимно простыми (числа называются взаимно простыми, если они не имеют общих делителей, кроме 1).
Во втором случае можно найти комбинацию, которая удовлетворяет уравнению: 5x + 2y = 1, например: x = 1, y = -2. А в первом случае уравнение 10x + 5y = 1 не имеет решений (если считать, что x и y – целые), так как левая часть равенства делится на 5, а правая – нет.
Во втором случае можно найти комбинацию, которая удовлетворяет уравнению: 5x + 2y = 1, например: x = 1, y = -2. А в первом случае уравнение 10x + 5y = 1 не имеет решений (если считать, что x и y – целые), так как левая часть равенства делится на 5, а правая – нет.
Раздел 3. Кодирование (15:45)
Полезным приложением теории чисел является кодирование. Все когда-нибудь пробовали говорить с другом на таком языке, который никто другой не поймет. Схожим образом устроена система кодирования: читать сообщения должен уметь тот, кто отправляет, и тот, кто принимает; при этом все остальные не должны понимать смысла этих сообщений, даже если перехватили их. Конечно, кодирование нужно не только для того, чтобы скрыть информацию, также оно нужно для увеличения устойчивости передаваемого сигнала.
Считается, что если код составлен человеком, то рано или поздно его можно разгадать. Задача кодирования – сделать так, чтобы это было поздно, а не рано, то есть продлить время, за которое код можно разгадать.
Дешифровка и математика
Как закодировать так, чтобы другие не узнали? Недавно вышел фильм об Алане Тьюринге, математике, который разгадал код «Энигма». Этим он существенно помог в победе над фашистской Германией. В то время в Германии думали, что этот шифр разгадать невозможно, поэтому использовали его всю войну. Но он был разгадан, так как за дело взялся продвинутый математик. Помимо этого, Тьюринг внес большой вклад в развитие информатики. Те, кому интересна тема шифрования, могут найти больше информации о машине Тьюринга, а также о нашем соотечественнике Кнорозове, который разгадал рукописи народов майя.
Идея, которая используются в открытом шифровании, математическая, и основана она на использовании простых чисел. Предположим, что задано какое-то большое число (1 152 349 694 119 649 281). Можно ли его разложить на произведение двух простых чисел? И если да, то на какие? То, что это сделать можно, дешифровщику известно, поэтому переформулируем задачу так: необходимо разложить число 1 152 349 694 119 649 281 на произведение двух простых чисел.
Название «открытое шифрование» связано именно с тем, что дешифровщик знает число, которое можно разложить (то есть знает текст передаваемого сообщения). Кажется, что задача несложная, нужно просто последовательно делить на простые числа, пока не найдём нужное. Но оказывается, что не существует эффективного алгоритма, который бы даже при современных мощностях компьютеров позволял бы представлять большие числа в виде произведения двух простых за небольшой промежуток времени.
Идея открытого шифра состоит в том, что с помощью определенного алгоритма можно закодировать сообщение в цифровом виде, то есть все символы определенным образом зашифровать так, чтобы получилось некоторое очень большое число. Это число открыто передается, мы не боимся, что его кто-то перехватит. У дешифровщика (которому мы передаем информацию) есть ключ, одно из простых чисел (один из двух множителей, на которые необходимо разложить отправленное число). Зная одно из чисел, он может получить делением второе число, а дальше с помощью известного алгоритма восстановить послание. Получается, что единственное, что нужно секретно передать дешифровщику, это ключ. Идея в том, что сам передаваемый код скрывать не нужно. То есть тот факт, что большое число нельзя быстро разложить на произведение двух простых, привел к созданию такого метода шифрования.
Ссылки на материалы InternetUrok.ru
1. Статья на Wikipedia «Криптосистема с открытым ключом»
2. Урок «Делители и кратное»
3. Урок «Признаки делимости на 10, на 5 и на 2»
4. Урок «Признаки делимости на 9 и на 3»
5. Урок «Простые и составные числа»
6. Урок «Разложение числа на множители»
7. Урок «Наибольший общий делитель. Алгоритм Евклида»
8. Урок «Наибольший общий делитель. Наименьшее общее кратное. Часть 1. НОД (Слупко М.В.)»
9. Урок «Наибольший общий делитель. Наименьшее общее кратное. Часть 2. НОК (Слупко М.В.)»
1. Статья на Wikipedia «Криптосистема с открытым ключом»
2. Урок «Делители и кратное»
3. Урок «Признаки делимости на 10, на 5 и на 2»
4. Урок «Признаки делимости на 9 и на 3»
5. Урок «Простые и составные числа»
6. Урок «Разложение числа на множители»
7. Урок «Наибольший общий делитель. Алгоритм Евклида»
8. Урок «Наибольший общий делитель. Наименьшее общее кратное. Часть 1. НОД (Слупко М.В.)»
9. Урок «Наибольший общий делитель. Наименьшее общее кратное. Часть 2. НОК (Слупко М.В.)»
Другие материалы