books

ТЕОРИЯ ЧИСЕЛ

Числа древних складывались из потребности обозначать количества, для счета они мало приспособлены. У египтян ближайшее основание (укрупнение числа), это десятка (сноп). Цифры до единицы они обозначали палочками. Римляне перевернули сноп и приблизили к началу, обозначили им пятерку V. Попробуйте сложить хотя бы IX и XVI, например. Египетским писцам ставили памятники.

Архимеду приписывают труд, под названием "Исчисление песчинок". Преимущество сети то, что на него можно посмотреть. Это не означает, что мы видим труд самого Архимеда. Мы видим то, что ему приписывают.

Цифры греки обозначали буквами, как точки на чертежах. При таком подходе только лишь обозначить большое количество, уже проблема. Заметим, что Архимед переписывался с александрийскими учеными. То есть, жил после основания Александрии, Мекки ученого мира, и пал от меча римского воина.

Тем более удивительно открытие Пифагором за два столетия до Александра македонского его теоремы. То есть, понимание и распространение указанного выше правила на все прямоугольные треугольники.

ЧИСЛА 3, 4, 5

Числа 3, 4 и 5. Они идут рядом, что обращает на них особое внимание. Наконец, они связаны со сторонами прямоугольного треугольника, ибо, как видно

32 + 42 = 52

Фотография пирамиды с пропорцией высоты и ширины 3:4

БОЯЗНЬ БЕСКОНЕЧНОСТИ

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

С бесконечно малым греки (и мы) знакомы по апориям Зенона. Недаром он почти современник Пифагора. Годится Пифагору во внуки. Апория о черепахе и Ахиллесе гласит, что самый быстрогоний герой Иллиады не догонит и черепахи. Ведь когда он добежит до того места, где она была, черепаха отползет. Так повторится бесконечное число раз. То, что Ахиллес таки опережает черепаху, отвечает жизненному опыту, но противоречит доводам разума. Противоречие неразрешимо, и греки вывели все доказательства, где встречается бесконечность, за пределы доверия.

Длина гипотенузы, того же сорта затруднение. Здравый смысл теорему Пифагора не приемлет. Ну и что? Подумаешь, серьезное опровержение. Однако при рассмотрении самого простого треугольника с единичными катетами высказанное Пифагором предположение поджидает хук уже не слева, а справа. Квадраты длин и гипотенузы, образуя пифагорову тройку, должны удовлетворять условию

1 + 1 = 2.

Дело за диагональю, а она не может быть целой. Египетская дробь содержит обозначения для долей одного предмета и, отдельно, 2/3. В отличие от египтян, греки вооружились для вычислений покрепче, пропорциями. Приделали к дроби множитель. Увы, и тут коса набегает на камень, ибо столь же ясными рассуждениями, как и со злосчастной ступенчатой линией, к всеобщему неудовольствию доказывается, что нет такой пропорции, которая будучи умножена сама на себя, даст 2.

ПРИКЛЮЧЕНИЯ ГИППАСА

Можно сказать, первый попавшийся под руку треугольник не существует в мыслимых греками мирах. Ничего не получается, с его расчетом. Когда первый попавшийся, это многое значит. Он невозможен ни так, ни этак. Все таки, если взять линейку, и посчитать множество треугольников, невольно утверждаешься в мысли, что квадрат гипотенузы таки равен суммам квадратов двух катетов. А историю с иррациональностью можно сделать тайной ордена пифагорейцев и посвящать в нее только избранных. Как передают седые предания, Пифагор преодолел последние терзавшие его сомнения и приказал изжарить по этому поводу сто быков. Теорема была провозглашена. Не потому ли пифагорейца-акусматика Гиппаса (египтянина?), разгласившего ужасную тайну математиков, безжалостно казнили. Тут история сильно рознится в версиях, почти как линия сюжета фильма "Мексиканец".

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

Самая знаменитая теорема, начинающая счет теоремам древности, в некотором смысле, неверна в атомарном пространстве Гераклита. Далее греки подзанялись греческими войнами и разбираться с позиционной записью числа и нерешенными проблемами предоставили иным народам. Поместив нажитое в сочинение Диофанта. Который жил не столь давно тому назад. В третьем столетии нашей эры. Тут сведения сильно рознятся, но это мелочь, ибо новый персонаж, советник Ферма, появляется на исторической сцене лет триста с довеском, опять же, назад. Вообще, три сотни лет нередко встречаются. За триста лет до нашей эры Александр сложил Александрию. Примерно к этому периоду времени относят творчество Евклида. Ньютон изобрел свой закон Ньютона примерно триста лет тому назад. Петербург недавно отпраздновал третье свое столетие. В общем, учить историю легко и приятно, если опираться на слово триста и знать о влиянии тройки на главную теорему математики.

Чтобы деление с остатком было однозначным, остаток считается положительным. Неполное частное от деления -5 на 3 равно -2, остаток 1.

АЛГОРИТМ ЕВКЛИДА

Античный человек, как и нынешний, измерял свой путь шагами. Это естественно, подсчитать, во сколько целых шагов укладывается пройденный путь.

Содержание древнейшего в истории человечества алгоритма состоит в том, что остаток пути оценить в шагах невозможно, но зато сам шаг можно измерить теперь полученным остатком пути. Ведь остаток заведомо меньше его. Величина шага принимается за новый путь, а остаток пути, за новый шаг. Ясно, что эту процедуру можно повторять и повторять, инвертируя, заменяя шаг остатком и уточняя величину пройденного пути. Построим наш первый алгоритм, обозначая путь как a, шаг как b, количество вхождений инвертируемого шага как q, остаток a-qb как r.


a=225, b=10, r=b,
while r>0, 
 q=floor(a/b), r=a-q*b, q=?,   
 if r>0, a=b, b=r, end, 
end,

Запустим исполняемый алгоритм для пути a=225 и шага b=10, получим последовательно количества вхождений (фракции) 22, 2. Измените a на 227, результаты изменятся на 22, 1, 2, 3. Результат применения алгоритма Евклида принято записывать в квадратных скобках, особо выделяя первое полученное число шагов в пути по сравнению с прочими количествами выбором особого знака разделения

225:10 = [22; 2], 227:10 = [22; 1, 2, 3].

Это напоминает запятую в десятичной записи числа, однако выделяемые разделителями количества - не цифры, а числа. Символ отношения a:b можно заменять дробной чертой a/b, тут, как и в школьных обозначениях пропорций или дробей, применительно к ситуации, непринципиально.

 books

НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ

Подпрограмму вычисления НОД в различных языках принято именовать gcd от "greatest common divisor", приведем и мы ее вариант, индифферентный к начальному соотношению чисел a и b.


a=225, b=10, r=gcd(a b), r=?, 

function: gcd(a b),
var q r R f, 
if b=0, R=a, else, R=b, r=b, 
while r>0, q=floor(a/b), R=r, 
r=a-q*b, if r>0, a=b, b=r, end, 
end, end, 
return R,
end,

 books

ЦЕПНАЯ ДРОБЬ

Цепная дробь раскрывает в привычных арифметических терминах то, что бы отношение исходных чисел a и b, оцененное при помощи алгоритма Евклида, значило

a/b = [q0; q1, ... , qn] = q0 + 1/(q1 + ...).

В данном выше примере примере

225/10 = [22; 2] = 22 + 1/2,

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

227/10 = 22 + 1/(1 + 1/(2 + 1/3)) = 22 + 1/(1 + 3/7) = 22 + 7/10.


a=225, b=10, r=fractions2(a b), r=?, 

function: fractions2(a b),
var q r R f, 
if b=0, f=[a 0], else, R=b, r=b, f=0,
while r>0, q=floor(a/b), 
if f=0, f=q, else, f={[f q]}, end,  
R=r, r=a-q*b, if r>0, a=b, b=r, end, 
end, end,
return f,
end,

СООТНОШЕНИЕ БЕЗУ

Представим остатки алгоритма Евклида линейными комбинациями a, b

r1 = a + b (-q0), r2 = a(-q0) + b(1 + q1q0), ... , rn = au + bv,

выражение для наибольшего общего делителя чисел a, b

rn = au + bv,

получаемого важным попутным продуктом применения алгоритма Евклида, называется соотношением Безу, а числа u и v - коэффициентами Безу.

Заметим, что цепная дробь a/b = [q0; q1, ... , qn] без последнего члена равна отношению коэффициентов Безу, взятому со знаком минус:

[q0; q1, ... , qn-1] = -v/u.

 books

ПРЕДСТАВЛЕНИЕ ЧИСЛА ЦЕПНОЙ ДРОБЬЮ

Число x представимо в виде конечной или бесконечной цепной дроби, согласно простому алгоритму фракции можно искать как целые части инверсных остатков

x = [q0; q1, ... , qn], q0=[1/x], q1=[1/(x-q0)], и т.п.

Например, число 1/3 = [0; 3] в десятичной системе представимо бесконечной записью 1/3=0.33333.., выгода очевидна.


x=1/3, f=fractions(x), f=?,

function: fractions(x),
var q r f, r=x, q=floor(x), 
f=q, r=r-q, for var i=0:20, 
if r>0.0000001, r=1/r, q=floor(r), 
f={[f q]}, r=r-q, else, break, end, 
end, return f,
end,

function: restore(f),
var i n, if typeof(f)=typeof(2), 
x=f, else, n=size(f), x=f[n], 
n=n-1, for i=n:-1:0, x=f[i]+1/x, end,
end, return x,
end,

Цепная дробь является периодической тогда и только тогда, когда число является квадратичной иррациональностью, т.е. имеет форму (a+b√c)/d, где c не является точным квадратом.

Сравнивая между собой вычислительные алгоритмы, можно посмотреть цепную дробь для √2 и π здесь (простейшая реализация) и в альфе

Периодичность: √2 - 2; √3 - 1,2; √5 - 4; √6 - 2,4; √7 - 1,1,1,4; √8 - 1,4; √10 - 6; √11 - 3,6.

Ограничим представление √2=1.4142136, видна неустойчивость фракций. Отсюда вопрос возникает, как по 9.6603 вылавливается (альфой) квадратичная иррациональность 1+5√3, ведь периодичность не проверить. Кстати, радикал из пяти, имеет более быструю сходимость, чем корни квадратные из 2, 3 и 7.

 books

ПОДХОДЯЩАЯ ДРОБЬ

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

a-1=1, a0=q0, an=qnan-1+an-2, b-1=0, b0=1, bn=qnbn-1+bn-2.


x=PI, f=fractions(x), 

n=2, a=rational2(f 1 n), b=rational2(f 0 n), 

[a b]=?, [x a/b]=?, 

function: rational2(f b n),
var i n r a b, 
if typeof(f)=typeof(2), 
if b>0, a=f, else, a=1, end, else, 
if n>size(f), n=size(f), end,
if b>0, a=f[0], else, a=1, end,
for i=1:n, r=f[i]*a+b, 
b=a, a=r, end, end, 
return a,
end, 

function: fractions(x),
var q r f, r=x, q=floor(x), 
f=q, r=r-q, for var i=0:20, 
if r>0.0000001, r=1/r, q=floor(r), 
f={[f q]}, r=r-q, else, break, end, 
end, return f,
end,

ТЕОРЕМА ФЕРМА

Советник Ферма прославился тем, что обратил внимание на следующее. Целые числа, удовлетворяющие уравнению из теоремы Пифагора

x2 + y2 = z2

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

x=p2 – q2, y=2pq, z=p2 + q2.

ГИПОТЕЗА ЭЙЛЕРА

Тут мы притормозим взмахи исторического маятника, и остановимся на расширительных толкованиях теоремы Ферма, возникших на почве ее долгой недоказуемости. Эйлер доказал утверждение Ферма на случай третьих степеней. Он же предложил выход из тупика, напрашивающийся ввиду того, что четверка чисел 3, 4, 5, 6 связана сходным выражением

33 + 43 + 53 = 63.

Почему бы степенному уравнению не набирать (для его разрешимости) вместе с показателем степени равное ему количество обязательных слагаемых? В начале прошлого века, казалось бы, нашлось подтверждение (Нори, 1911 год)

304+1204+2724+3154 = 3534.

Спустя полвека свое веское слово сказали, наконец, компьютеры. Контрпример К. Дж. Леидера и Т. Р. Паркина (L. J. Lander, T. R. Parkin, 1966 года) одним росчерком цифрового кода развалил эту красивую гипотезу

275 + 845 + 1105 + 1335 = 1445.

В 1988 году Наум Элькис из Гарвардского университета нашел еще и следующее решение:

26824404 + 153656394 + 1879604 = 206156734

Так компьютерные эксперименты поставили точку на попытке поиска решения, закрываемого теоремой Ферма.

РАЗЛОЖЕНИЕ НА СУММУ КВАДРАТОВ

Еще Жирар и, позднее, Ферма заметили, что любое натуральное число представляется суммой (не более, чем) четырех квадратов целых чисел. Эйлер подробно рассмотрел вопрос о двух слагаемых, тут сквозит нечто близкое пифагоровым тройкам

x2 + y2 = z.

Этим уравнением плотно занимались уже не античные мифические греки, а наши современники. В 1749 году, после семи лет работы и почти через сто лет после смерти Ферма, Эйлеру удалось доказать теорему о простых числах, согласно которой разложение на сумму квадратов всегда возможно для чисел 4k+1. Ни одно число вида 4k+3 не представимо в виде суммы двух квадратов. Число, содержащее в своем разложении лишь четные степени 4k+3, может быть представлено в виде суммы двух квадратов. Если отбросить заведомо не представимые суммой двух квадратов числа, то это 1, 2, 4, 5, 8, 9, 10, 13, 16, 17, 18, 20, ... Числа типа 4k+1 представимы всегда.

Известны сложные схемы решения, принадлежащие Лежандру, Гауссу, Серру и Якобсталю. Основная теорема арифметики гласит, что любое число может быть представлено, причем, единственным образом (с точностью до перестановок) произведением простых чисел. Определение простого числа оперирует произведением, сложение - сторонняя операция для него. Путь к суммам тернист и пролегает через решение проблемы Гольдбаха.

ПРОБЛЕМА ГОЛЬДБАХА

В 1742 году немецкий математик Христиан Гольдбах в письме к своему другу и коллеге Леонарду Эйлеру (переписка опубликована) высказал одно очень простое утверждение. "Всякое целое число, большее или равное шести, может быть представлено в виде суммы трех простых чисел", - написал Гольдбах. Эйлер заметил в ответном письме, что проблема сводится к доказательству того, что каждое четное число есть сумма двух простых. Эта проблема, решения

x + y = z,

получила название "Проблемы Гольдбаха", и ее доказательство до сих пор не найдено.

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

6 = 3 + 3, 8 = 3 + 5, 10 = 3 + 7, 12 = 5 + 7, ...

Можно взять сколь угодно большое число, и гипотеза окажется верна.

Следующий график количества вариантов разложения взят из обзора Тима Скоренко.

Проблема состоит именно в том, чтобы найти общее математическое доказательство утверждения Гольдбаха. Характерно то, что Гольдбах не был светилом математической науки своего времени. Он родился в 1690-м году и закончил юридический факультет Кенигсбергского университета: математика была всего лишь его хобби. В 1725-м году Гольдбах приехал в Россию, где получил звание академика Петербургской академии наук, а с 1742 года работал в Коллегии иностранных дел.

С Эйлером он вел дружескую переписку в течение 35 лет, вплоть до своей смерти в 1764 году в Москве. В 1843-м году 177 писем этой переписки были опубликованы. Он довольно много путешествовал и дружил с многими известными математиками, в том числе с семьей Бернулли. За свою жизнь он опубликовал менее десятка некрупных математических работ, хотя две из них – о бесконечных рядах – сделали его достаточно известным в научных кругах. Впрочем, в широких кругах Христиан Гольдбах стал известен благодаря нескольким фразам в одном-единственном письме к своему другу. Такие вот игры судьбы.

КОНЕЧНЫЙ НАБОР ЧИСЕЛ

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

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

Можно не отбрасывать лишние числа, а договориться, что часть из них обозначает одно и то же, как тут (предметы дает нижний ряд)

0 1 2 3 4 5 6 7 8 9 ..
0 1 2 0 1 2 0 1 2 0 ..

Если мы матерчатый метр, который используют портняжки, намотаем на палец, то возникает примерно такая система чисел. Количество принимаемых во внимание предметов (различных между собой чисел нижнего ряда) называют модулем, в данном случае m=3, а когда хотят сопоставить числу верхнего ряда обозначаемый им предмет (число нижнего ряда), пишут так

4 ≡ 1 (mod 3)

В общем,

a ≡ b (mod m)

означает просто, что a – b делится нацело на m. Поскольку числа, равные или большие по значению m, всего лишь обозначения, вычисления с ними с некоторыми оговорками можно заменить вычислениями с числами 0, 1, ... , m-1.

ЕЩЕ ОДНА ТЕОРЕМА ФЕРМА

Разместим в нижнем ряду значения квадратов чисел по модулю m=3

0 1 2 3 4 5 6 7 8 9 ..
0 1 1 0 1 1 0 1 1 0 ..

Такие наблюдения привели Ферма к обобщению, что если модуль m простой, то степень m – 1 любого a (не сравнимого с нулем) тождественна 1

am – 1 ≡ 1 (mod m)

Заметим, что для простого m число φ(m) = m – 1 означает количество чисел, меньших m и взаимно простых с m.

Свойство помечать единицей степени заинтересовало Эйлера, и он выяснил, что для любого m показатель (функция Эйлера) сохраняет отмеченное качество. Так m = 20 взаимно просто с 1, 3, 7, 9, 11, 13, 17, 19, т.е. φ(20) = 8. Обобщение Эйлером теоремы такое

aφ(m) ≡ 1 (mod m).

Минимальный показатель степени уравнения называется порядком числа a. Например, a=5 и m=11 взаимно просты, m - простое. Порядок числа 5 равен φ(m) = m – 1 = 10, т.е. 510 ≡ 1 (mod 11).

КВАДРАТИЧНЫЕ ВЫЧЕТЫ

Теорема Ферма

am – 1 ≡ 1 (mod m)

вводит, по сути, понятие корня из 1 по модулю m. Свойство степенного уравнения иметь корни зависит от значения правой части, варьируемой (в общем) в диапазоне от 1 до m–1. Важные для теории сравнения значения, дающие разрешимые уравнения, называются вычетами (остальные невычетами).

Рассмотрим, например, квадраты последовательности натуральных чисел по модулю m=13

1 4 9 3 12 10 10 12 3 9 4 1

Квадратичные уравнения с правыми частями 1, 3, 4, 9, 10, 12 разрешими в целых числах, это вычеты. Остальные числа 5, 6, 7, 8, 11 - квадратичные невычеты. Множество 1, 2, ..., m–1, на котором ищутся квадратичные вычеты, избыточно, оно симметрично относительно середины интервала, ибо

(m – a)2 ≡ a2 (mod m).

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

СИМВОЛЫ ЛЕЖАНДРА

Свойство числа a быть или не быть вычетом по модулю m напоминает булеву функцию со значениями ±1. Сохранилось идущее от Лежандра дробное обозначение ее (a/m), поскольку она обладает мультипликативным свойством

(ab/m) = (a/m)(b/m).

КРИТЕРИЙ ЭЙЛЕРА

Вернемся к теореме Ферма, переписав ее как

aM ≡ ±1 (mod m)

где M = (m – 1)/2 (половина степени), т.е. аппроксимациям

m=4k+1: 1 5 9 13 17 21 ... m=4k+3: 3 7 11 15 19 23 ...

отвечают четные и нечетные числа M соответственно.

В терминах символов Лежандра теорема Ферма записывается в форме критерия, предложенного Эйлера

(a/m) = aM (mod m)

Из критерия следует, в частности, что число a = –1 есть квадратичный вычет для четных M, и квадратичный невычет для нечетных.

Тот факт, что сравнение a2 + 1 ≡ 0 (mod m) разрешимо для простых вида 4k+1 и неразрешимо для простых вида 4k+3, отмечал еще Ферма.

ЗАКОН ВЗАИМНОСТИ

Квадратичный закон взаимности, сформулированный Лежандром для двух простых чисел a и m, имеет вид

(a/m)(m/a) = (–1)MA,

где M = (m – 1)/2, A = (a – 1)/2. Он позволяет упрощать выкладки, сменой модуля.

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



Rambler's Top100