?

Log in

No account? Create an account
о греках и простых числах (математическое) - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

о греках и простых числах (математическое) [фев. 1, 2013|10:19 pm]
Anatoly Vorobey
[Tags|]

Наверное, многие знают, и не только физики, но и лирики, что любое натуральное число можно разложить на простые множители (например, 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. Я планирую написать отдельную запись о доказательствах основной теоремы арифметики.
СсылкаОтветить

Comments:
From: posic
2013-02-01 08:27 pm
Основная теорема арифметики.
(Ответить) (Thread)
[User Picture]From: avva
2013-02-01 08:28 pm
Да, спасибо; причем знал, когда готовил черновик, а потом переписал и все равно из английского скалькировал. Сейчас исправлю везде, спасибо.
(Ответить) (Parent) (Thread)
From: nedosionist
2013-02-01 08:30 pm
одно из них не простое - что, может быть, равны?
Не может быть, в силу той же теоремы.
(Ответить) (Thread)
[User Picture]From: avva
2013-02-01 09:09 pm
Да, это верно, должно быть "некоторые из них не простые".
(Ответить) (Parent) (Thread)
[User Picture]From: salas
2013-02-01 08:32 pm
Мы не знаем, как в точности он доказал иррациональность корней от 3 до 17; наверняка это было не с помощью подробного пересчета остатков и квадратов
Почему бы и нет? Правда, конечно, идея арифметики остатков очевидна тоже не была, но в какую другую сторону можно обобщить мысль, что квадрат нечётного нечётен?
(Ответить) (Thread)
[User Picture]From: vanxant
2013-02-02 03:11 am
Вот именно. Даже в современной арифметике, если нужно найти последнюю цифру записи, например, 7 в степени 7 в степени 7 (и так 7 раз) - как раз таки подробно пересчитывают остатки (в данном случае по модулю 10).
(Ответить) (Parent) (Thread)
[User Picture]From: goliafffff
2013-02-01 08:37 pm
Большое спасибо за небольшой, но очень интересный экскурс в историю математики!
(Ответить) (Thread)
[User Picture]From: inkogniton
2013-02-01 08:48 pm
Насколько я знаю/читала доказательство иррациональности квадратного корня из двух принадлежит Евклиду -- в нём же в первый раз использован метод доказательства от противного, который тоже, соответственно, приписывается Евклиду. Пифагор, насколько я знаю/читала, отрицал существование иррациональных чисел в принципе. Более того, существует легенда, что он приказал казнить одного из своих учеников именно за то, что тот попытался задать вопрос о рациональности квадратного корня из двух.

Edited at 2013-02-01 20:49 (UTC)
(Ответить) (Thread)
From: ztarlitz
2013-02-02 02:07 pm
Вроде скинули в море того кто доказал, или сам скинулся от горя, потому что пифагорейцы были помешаны на натуральных числах. И признать, что реальный мир описать натуральными числами не получится, было им тяжело.
(Ответить) (Parent) (Thread)
[User Picture]From: ilya_dogolazky
2013-02-01 09:27 pm
Представление о том, что простые числа это типа атомов, из которых состоят все прочие числа к сожалению не делает теорему очевидной --- оно лишь делает таковым часть "единственность", а вот что в каждом числе лишь конечное число "атомов" (то есть часть "существование разложения") как раз остаётся неочевидным.
(Ответить) (Thread)
From: huzhepidarasa
2013-02-02 09:26 am
существование очевидно само по себе.
(Ответить) (Parent) (Thread)
[User Picture]From: yoksel_moksel
2013-02-01 09:39 pm
Я не представлял простые числа в виде атомов, для меня атомом была единица, поэтому никогда единственность разложения на простые множители не была для меня очевидной.
(Ответить) (Thread)
[User Picture]From: bortans
2013-02-01 10:11 pm
Аналогично. "Атомы" это нечто одинаковое и минимальное по размерам (по-крайней мере, с упрощенной точки зрения; хотя, конечно, стоит лучше говорить об "элементарных частицах"). А простые множители все разные и могут быть очень большими.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: buddha239
2013-02-01 10:33 pm
Студентам, к сожалению, бывает очевидна даже единственность разложения на произвольные множители, так что доказывать надо!:) Но гораздо интереснее числа классов считать!
(Ответить) (Thread)
[User Picture]From: murchik007
2013-02-01 10:57 pm
Очень интересная запись.

обязательно перечитаю завтра - на трезвую голову
(Ответить) (Thread)
[User Picture]From: southwest
2013-02-01 11:29 pm
с бодуна также хорошо подумать и о том, что самое знаменитов первое доказательство теоремы Ферма (великой) было как раз основано на заблуждении, что раскладывание на простые числа однозначно во всех "хороших" кольцах, не только в целых числах

http://en.wikipedia.org/wiki/Fermat%27s_Last_Theorem#Ernst_Kummer_and_the_theory_of_ideals

(Ответить) (Parent) (Thread)
[User Picture]From: olkab
2013-02-02 06:23 am
Спасибо. Ужасно интересно.
(Ответить) (Thread)
[User Picture]From: kray_zemli
2013-02-02 07:10 am
Очевидность единственности разложения естественным образом закрепляется длительной дрючки дробями в школе. Потому что если разложение не единственно, то дроби имели бы по несколько вариантов полного сокращения, а из дрючки мы хорошо помним, что так не бывает, и правильный ответ всегда один.

А всякие там ваши основные теоремы арифметики уже потом проходят.
(Ответить) (Thread)
[User Picture]From: trupodur
2013-02-04 02:27 pm
это ваше рассуждение, что ли, приложимо только к таким составным числам, которые раскладываются на два простых члена.
(Ответить) (Parent) (Thread)
From: ztarlitz
2013-02-02 02:03 pm
Интересно. Но на сколько я могу судить( это не известно) доказательство пифагорейцев иррациональности корня скорее геометрическое.

Еще мне всегда было интересно, а были ли до пифагорейцев какие-нибудь доказательства в математике? Сходу не могу ничего вспомнить чтобы что-то доказывали.
(Ответить) (Thread)
From: asox
2013-02-02 06:02 pm
Харди рассказывает, что одним из учителей Платона был Феодор Киренский, математик пифагоровской школы.

Так учитель или ученик? Из последующего изложения создаётся впечатление, что - второе.
А саму теорему - не знал, посыпаю пеплом голову. Но, по-моему это - вещь почти очевидная.

Предположим 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 - он тоже не делится нацело
(Ответить) (Thread)
[User Picture]From: avva
2013-02-02 06:40 pm
Феодор был учителем Платона, как я понимаю, и возможно чем-то вроде ученика ученика Пифагора.

Ваше док-во опирается на так называемую лемму Евклида, которая говорит следующее: если произведение ab делится на простое p, то либо a, либо b отдельно делятся на p (либо и то и другое). У вас c*d делится на b, и вы заключаете, что b должно делить либо d, либо c.

Но лемму Евклида тоже еще надо доказать.

Если точнее, не совсем так. Ваше заключение вы обосновываете с помощью следующего общего утверждения: если a/b сокращенная дробь, то сделать ее целой, умножив на что-то, можно только с помощью умножения на число кратное b. Это верное утверждение, но оно тоже требует доказательства, и более того, оно включает в себя лемму Евклида как частный случай (когда b простое). Общая более строгая формулировка этого утверждения следующая: если a и b взаимно простые числа, и b делит ac, то b делит c.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: falcao
2013-02-03 01:46 am

иррациональность без ОТА

Я вот тут вспомнил по ходу дела о доказательстве иррациональности корня из двух, которое Вы как-то приводили у себя в журнале. Там Основная Теорема Арифметики не использовалась. Почти то же самое рассуждение, применённое к корню из любого натурального числа, не являющемуся точным квадратом, приводит к нужному результату.

Для тех, кто не помнит или не знает, о чём речь, коротко изложу суть. Пусть n -- натуральное, но не точный квадрат. Требуется доказать, что x = n1/2 иррационально. Допустим, что это не так, и пусть тогда x представлено как частное двух натуральных чисел с наименьшим возможным значением q в знаменателе. Покажем, как уменьшить q, придя тем самым к противоречию.

Обозначим через k целую часть числа x. Ясно, что x не равно k. Но тогда разность x-k лежит строго между 0 и 1, то есть представляется "правильной" дробью. Знаменатель при вычитании k не изменился, то есть получилось x-k=p/q, где p меньше q.

Теперь рассмотрим обратные величины, то есть q/p=1(x-k)=(x+k)/(x^2-k^2)=(x+k)/(n-k^2). Домножая, получаем q(n-k^2)/p=x+k, то есть x+k имеет вид дроби со знаменателем p, меньшим q. Вычитание целого числа k знаменателя не меняет, QED.
(Ответить) (Thread)
[User Picture]From: a_konst
2013-02-04 12:53 pm
Класс. Но это далеко не просто придумать.

Но доказательство с использованием ОТА действительно очевидно, и то, что Феодор остановился на 17, пожалуй, показывает, что сама ОТА была ему неизвестна или неочевидна.
(Ответить) (Parent) (Thread) (Развернуть)