о греках и простых числах (математическое)
Feb. 1st, 2013 10:19 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaНаверное, многие знают, и не только физики, но и лирики, что любое натуральное число можно разложить на простые множители (например, 120 = 2*2*2*3*5), и что такое разложение есть только одно, оно единственно. Что это значит? Понятно, что можно поменять множители местами - например, 120 = 5*3*2*2*2. Но любое разложение 120 на простые множители включает в себя ровно три двойки, одну тройку и одну пятерку. Никакие другие простые множители типа 7 или 23 не могут там появиться, а те, что есть, обязаны повторяться ровно это число раз.
Эти два факта - что можно разложить на простые множители, и что такое разложение единственно - вместе называются "основная теорема арифметики". Когда студентам-математикам преподают эту теорему и ее доказательство, часто бывает, что им трудно понять, что тут есть доказывать. Ведь это же совершенно тривиально и очевидно! Что ж, то, что разложение на простые множители существует, действительно тривиально, но то, что оно единственно, только кажется очевидным - это утверждение, которое требует своего доказательства, пусть не очень сложного, но настоящего.
Британский математик Тимоти Гоуэрс написал целую запись об том, почему основная теорема арифметики на самом деле не очевидна: Why isn’t the fundamental theorem of arithmetic obvious? Не буду повторять все его аргументы, но приведу один: действительно ли очевидно нам, не вычисляя, что 23*1759 не равно 53*769? Если я вам скажу, что все четыре числа простые, неужели вам немедленно станет очевидно (не ввиду этой теоремы, а непосредственным восприятием), что произведения не равны, а если окажется, что я соврал и одно из них не простое - что, может быть, равны?
Мне кажется, после знакомства с понятием разложения на простые множители наше воображение рисует нам такую картинку, в которой каждое число как бы составлено из "атомов", его простых множителей, и каждое простое число - как бы "атом" разного "элемента". В такой картинке действительно очевидно, что есть только одно разложение - на те "атомы", из которых число собственно состоит. Но, как бы это сказать, легитимность этой картинки собственно опирается на единственность разложения в основной теореме, и поэтому эта очевидность обманчива - она скрывает тот факт, что что-то действительно нужно доказать.
Мне попался недавно замечательный пример того, что это на самом деле неочевидно - его привел знаменитый английский математик Харди в 1929 году. Харди известен помимо прочего своим классическим учебником "Введение в теорию чисел", в соавторстве с Райтом. Он вышел в свет в 1938 году, но до того, в 1929 году, Харди прочитал публичную лекцию под тем же названием (кстати, очень интересную, рекомендую к прочтению).
Как известно, древние греки еще во времена Пифагора обнаружили, что квадратный корень из двух - иррациональное число (открытие приписывается самому Пифагору, но точно это неизвестно). Пифагор жил в 6-м веке до нашей эры, за сто лет до Сократа и Платона. Харди рассказывает, что одним из учителей Платона был Феодор Киренский, математик пифагоровской школы. Мы знаем о нем потому, что Платон рассказал о нем немного в двух своих диалогах, и в частности там упомянуто, что Феодор доказал иррациональность всех квадратных корней из чисел от 3 до 17 (не включая, конечно, те числа, которые действительно являются целыми квадратами, то есть 4, 9 и 16: два, три и четыре в квадрате). Про корень из двух ему не надо было доказывать, это было известно со времен Пифагора, а вот от 3 до 17 было его собственным вкладом, который в то время высоко оценили современники.
Позвольте напомнить вам греческое доказательство иррациональности корня из двух, весьма простое. Предположим, что корень из двух на самом деле рационален и равен дроби A/B, и это сокращенная дробь - A и B уже нельзя вместе сократить еще больше. Если мы возведем в квадрат обе части A/B = √2, то увидим, что A2/B2 = 2 или A2 = 2B2. Отсюда следует, что A2 четное число, значит, и A четное, то есть можно записать A = 2*C. Тогда A2 = 4C2 = 2B2, и отсюда B2 тоже четное, и значит, B четное. Но это значит, что A и B вместе можно сократить, потому что они оба делятся на 2 - а это противоречит тому, с чего мы начали. Значит, наше начальное предположение было неверно и √2 нельзя записать как дробь, что и требовалось доказать.
В этом доказательстве я выделил ключевую часть, на которой основан весь аргумент. Почему это верно, что из "A2 четное число" следует "A четное", и то же самое для B? Это действительно очевидно - это следует из того, что квадрат нечетного числа остается нечетным - и легко строго доказать: запишем нечетное число в виде 2k+1 для какого-то k, возведем в квадрат, раскроем все скобки, упростим и увидим, что получится опять нечетное.
Но теперь представим себе, что вместо √2 мы хотим доказать теорему для √5. У нас опять будет тот же ключевой шаг, который выглядит так: из
"A2 делится на пять" следует "A делится на пять". Как это доказать? Можно опять напрямую, но придется отдельно рассмотреть все возможные числа, которые не делятся на пять (то есть, дают остаток 1, 2, 3 или 4), и для каждого вида отдельно доказать, что его квадрат опять не делится. Это громоздко, длинно, и нужно отдельно делать для каждого числа. Можно намного проще! Просто представьте себе разложение A на простые множители. Если в нем нет пятерки, то и в разложении A2, в котором ровно те же множители, повторенные дважды, ее тоже нет, вот и все доказательство.
Почему же тогда, задает Харди риторический вопрос, Феодор Киренский написал длинный трактат о том, как доказать иррациональность чисел от 3 до 17, и почему только до 17? Ведь обычное доказательство для двойки тривиальным образом обобщается на все эти случаи, да и для чисел больше 17 тоже! Что же он там доказывал?
(если быть немного точнее, то вышеприведенный аргумент для пятерки работает для всех "бесквадратных чисел", в которых простые множители повторяются не больше одного раза; например, 5, 7, 10 = 2*5 или 15 = 5*3, но не 12 = 2*2*3. Но из таких чисел как 12, всегда можно заранее "вытащить" их квадратную часть: √12 = √(2*2*3) = 2*√3 - и доказать иррациональность того, что осталось).
Так вот, разгадка состоит в том, что очевидное для нас разложение чисел на простые множители единственным способом - основная теорема арифметики - была, увы, Феодору неизвестна. Ее сформулировал (не целиком, но почти целиком) Евклид, в седьмой и девятой книгах своих "Элементов", около 300 г. до нашей эры. Феодор умер за сто лет до того, и то, что для нас совершенно "очевидно", ему было недоступно. Мы не знаем, как в точности он доказал иррациональность корней от 3 до 17; наверняка это было не с помощью подробного пересчета остатков и квадратов, но как именно? - современные математики выдвинули несколько разных гипотез. Но для его времени, не знавшего "очевидную" основную теорему арифметики, это действительно было выдающимся достижением.
P.S. Я планирую написать отдельную запись о доказательствах основной теоремы арифметики.
Эти два факта - что можно разложить на простые множители, и что такое разложение единственно - вместе называются "основная теорема арифметики". Когда студентам-математикам преподают эту теорему и ее доказательство, часто бывает, что им трудно понять, что тут есть доказывать. Ведь это же совершенно тривиально и очевидно! Что ж, то, что разложение на простые множители существует, действительно тривиально, но то, что оно единственно, только кажется очевидным - это утверждение, которое требует своего доказательства, пусть не очень сложного, но настоящего.
Британский математик Тимоти Гоуэрс написал целую запись об том, почему основная теорема арифметики на самом деле не очевидна: Why isn’t the fundamental theorem of arithmetic obvious? Не буду повторять все его аргументы, но приведу один: действительно ли очевидно нам, не вычисляя, что 23*1759 не равно 53*769? Если я вам скажу, что все четыре числа простые, неужели вам немедленно станет очевидно (не ввиду этой теоремы, а непосредственным восприятием), что произведения не равны, а если окажется, что я соврал и одно из них не простое - что, может быть, равны?
Мне кажется, после знакомства с понятием разложения на простые множители наше воображение рисует нам такую картинку, в которой каждое число как бы составлено из "атомов", его простых множителей, и каждое простое число - как бы "атом" разного "элемента". В такой картинке действительно очевидно, что есть только одно разложение - на те "атомы", из которых число собственно состоит. Но, как бы это сказать, легитимность этой картинки собственно опирается на единственность разложения в основной теореме, и поэтому эта очевидность обманчива - она скрывает тот факт, что что-то действительно нужно доказать.
Мне попался недавно замечательный пример того, что это на самом деле неочевидно - его привел знаменитый английский математик Харди в 1929 году. Харди известен помимо прочего своим классическим учебником "Введение в теорию чисел", в соавторстве с Райтом. Он вышел в свет в 1938 году, но до того, в 1929 году, Харди прочитал публичную лекцию под тем же названием (кстати, очень интересную, рекомендую к прочтению).
Как известно, древние греки еще во времена Пифагора обнаружили, что квадратный корень из двух - иррациональное число (открытие приписывается самому Пифагору, но точно это неизвестно). Пифагор жил в 6-м веке до нашей эры, за сто лет до Сократа и Платона. Харди рассказывает, что одним из учителей Платона был Феодор Киренский, математик пифагоровской школы. Мы знаем о нем потому, что Платон рассказал о нем немного в двух своих диалогах, и в частности там упомянуто, что Феодор доказал иррациональность всех квадратных корней из чисел от 3 до 17 (не включая, конечно, те числа, которые действительно являются целыми квадратами, то есть 4, 9 и 16: два, три и четыре в квадрате). Про корень из двух ему не надо было доказывать, это было известно со времен Пифагора, а вот от 3 до 17 было его собственным вкладом, который в то время высоко оценили современники.
Позвольте напомнить вам греческое доказательство иррациональности корня из двух, весьма простое. Предположим, что корень из двух на самом деле рационален и равен дроби A/B, и это сокращенная дробь - A и B уже нельзя вместе сократить еще больше. Если мы возведем в квадрат обе части A/B = √2, то увидим, что A2/B2 = 2 или A2 = 2B2. Отсюда следует, что A2 четное число, значит, и A четное, то есть можно записать A = 2*C. Тогда A2 = 4C2 = 2B2, и отсюда B2 тоже четное, и значит, B четное. Но это значит, что A и B вместе можно сократить, потому что они оба делятся на 2 - а это противоречит тому, с чего мы начали. Значит, наше начальное предположение было неверно и √2 нельзя записать как дробь, что и требовалось доказать.
В этом доказательстве я выделил ключевую часть, на которой основан весь аргумент. Почему это верно, что из "A2 четное число" следует "A четное", и то же самое для B? Это действительно очевидно - это следует из того, что квадрат нечетного числа остается нечетным - и легко строго доказать: запишем нечетное число в виде 2k+1 для какого-то k, возведем в квадрат, раскроем все скобки, упростим и увидим, что получится опять нечетное.
Но теперь представим себе, что вместо √2 мы хотим доказать теорему для √5. У нас опять будет тот же ключевой шаг, который выглядит так: из
"A2 делится на пять" следует "A делится на пять". Как это доказать? Можно опять напрямую, но придется отдельно рассмотреть все возможные числа, которые не делятся на пять (то есть, дают остаток 1, 2, 3 или 4), и для каждого вида отдельно доказать, что его квадрат опять не делится. Это громоздко, длинно, и нужно отдельно делать для каждого числа. Можно намного проще! Просто представьте себе разложение A на простые множители. Если в нем нет пятерки, то и в разложении A2, в котором ровно те же множители, повторенные дважды, ее тоже нет, вот и все доказательство.
Почему же тогда, задает Харди риторический вопрос, Феодор Киренский написал длинный трактат о том, как доказать иррациональность чисел от 3 до 17, и почему только до 17? Ведь обычное доказательство для двойки тривиальным образом обобщается на все эти случаи, да и для чисел больше 17 тоже! Что же он там доказывал?
(если быть немного точнее, то вышеприведенный аргумент для пятерки работает для всех "бесквадратных чисел", в которых простые множители повторяются не больше одного раза; например, 5, 7, 10 = 2*5 или 15 = 5*3, но не 12 = 2*2*3. Но из таких чисел как 12, всегда можно заранее "вытащить" их квадратную часть: √12 = √(2*2*3) = 2*√3 - и доказать иррациональность того, что осталось).
Так вот, разгадка состоит в том, что очевидное для нас разложение чисел на простые множители единственным способом - основная теорема арифметики - была, увы, Феодору неизвестна. Ее сформулировал (не целиком, но почти целиком) Евклид, в седьмой и девятой книгах своих "Элементов", около 300 г. до нашей эры. Феодор умер за сто лет до того, и то, что для нас совершенно "очевидно", ему было недоступно. Мы не знаем, как в точности он доказал иррациональность корней от 3 до 17; наверняка это было не с помощью подробного пересчета остатков и квадратов, но как именно? - современные математики выдвинули несколько разных гипотез. Но для его времени, не знавшего "очевидную" основную теорему арифметики, это действительно было выдающимся достижением.
P.S. Я планирую написать отдельную запись о доказательствах основной теоремы арифметики.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2013-02-02 06:02 pm (UTC)Так учитель или ученик? Из последующего изложения создаётся впечатление, что - второе.
А саму теорему - не знал, посыпаю пеплом голову. Но, по-моему это - вещь почти очевидная.
Предположим a, b, c и d - простые числа и:
a * b = c * d
Тогда:
a = c * d / b
Т.к. все числа целые, то правая часть - целая. Соответственно у нас либо d / b - целое, либо с, умноженное на всю дробь d/b - целое.
Первое утверждение противоречит тому, что d и b - простые.
Что-бы d/b, домноженное на c стало целым - знаменатель сокращённой дроби d/b должен делить c нацело.
d/b не сокращается - т.к числа простые, т.е. необходимо рассмотреть c/b. c/b - не делится на цело аналогично d/b.
Дальше надо по индукции рассматривать случаи нескольких множителей.
Так вроде.
Второе утверждение предполагает, что мы должны рассмотреть сокращённую дробь d/b. Но т.к. эти числа простые - то дробь несократима. Рассмотрим c/b - он тоже не делится нацело
no subject
Date: 2013-02-02 06:40 pm (UTC)Ваше док-во опирается на так называемую лемму Евклида, которая говорит следующее: если произведение ab делится на простое p, то либо a, либо b отдельно делятся на p (либо и то и другое). У вас c*d делится на b, и вы заключаете, что b должно делить либо d, либо c.
Но лемму Евклида тоже еще надо доказать.
Если точнее, не совсем так. Ваше заключение вы обосновываете с помощью следующего общего утверждения: если a/b сокращенная дробь, то сделать ее целой, умножив на что-то, можно только с помощью умножения на число кратное b. Это верное утверждение, но оно тоже требует доказательства, и более того, оно включает в себя лемму Евклида как частный случай (когда b простое). Общая более строгая формулировка этого утверждения следующая: если a и b взаимно простые числа, и b делит ac, то b делит c.
no subject
Date: 2013-02-02 07:13 pm (UTC)Если точнее, не совсем так. Ваше заключение вы обосновываете с помощью следующего общего утверждения: если a/b сокращенная дробь, то сделать ее целой, умножив на что-то, можно только с помощью умножения на число кратное b. Это верное утверждение, но оно тоже требует доказательства, и более того, оно включает в себя лемму Евклида как частный случай (когда b простое). Общая более строгая формулировка этого утверждения следующая: если a и b взаимно простые числа, и b делит ac, то b делит c.
Только непонятно, почему необходимо доказывать, что нецелое a/b для превращения в целое - требует домножения на (n)b. Тем более, что все числа по условию - простые.
no subject
Date: 2013-02-02 07:17 pm (UTC)Ну вот нецелому 4/6 для превращения в целое хватает домножения только на 3. Конечно, 4/6 - не сокращенная дробь, но это показывает, что сокращенность дроби нужно как-то использовать в доказательстве того, что умножить необходимо на (n)b, и ничто другое не пройдет.
no subject
Date: 2013-02-02 07:27 pm (UTC)no subject
Date: 2013-02-02 07:43 pm (UTC)no subject
Date: 2013-02-02 08:11 pm (UTC)c * (d/b)
Все числа простые и различные.
Дробь несократима, т.к. d и b - простые числа.
Соответственно что-бы дробь была целой - знаменатель должен быть равен единице или d, потому, что простое d делится нацело только на себя или на 1. Т.е. в d/(b/c) величина b/c = 1, но это невозможно, т.к. b - простое.
Если b/c = d, то b = d * c - это тоже невозможно, т.к. b - простое.