теория чисел

Автостопом по математике

Остановка 2

Будем считать, что в первом приближении мы освоились с этим «бесконечно таинственным» объектом ℕ – множеством натуральных чисел. Давайте заглянем внутрь него повнимательнее: что мы там сумеем обнаружить, кроме бесконечности?

Наверное, первое, что обращает на себя внимание – это арифметические операции сложения и умножения, относительно которых множество натуральных чисел замкнуто.

Р. Голдблатт «Топосы. Категорный анализ логики» (стр. 43)

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

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

И, наверное, так же понятно, что с вычитанием и делением это далеко не всегда так.

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

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

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

0

А что, если мы заменим умножение сложением? Чего нам будет недоставать, чтобы продолжать считать множество ℕ моноидом? Правильно, «единицы», роль которой в данном случае несомненно играет ноль. Доложим его в ℕ и будем обозначать ℕ . полученное множество с присоединённым к нему нулём.

Э. Б. Винберг «Начала алгебры»

Примеры алгебраических структур здесь:

Пересадка

Мы видели, что каждое натуральное число есть сумма единиц. Но складывать с собой мы можем не только единицу, но и любое другое натуральное число, и прибавление натурального числа n к себе самому m раз мы, собственно, и называем умножением.

Мы же продолжим выбранный путь

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

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

Давайте выпишем их для начала побольше – скажем, все от 1 до 1000 – и посмотрим:

Получилось ровно 168 штук. Причём, кажется, что они редеют. В диапазоне от 1 до 100 их 25, от 401 до 500 — уже 17, а между 901 и 1000 – 14. Если бы мы продлили список до миллиона, то обнаружили бы в последней сотне от 999 901 до 1 000 000 всего восемь простых, а среди последней сотни чисел до триллиона включительно их вообще четыре.
Будет ли так продолжаться всегда?

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

Что ещё можно заметить в отношении простых чисел?

Уверены, на первое время вам хватит…)

Действительно ли доля простых чисел среди всех натуральных становится все меньше, и, значит, можно утверждать, что большинство натуральных чисел не являются простыми?

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

Теорема о распределении простых чисел даёт на этот вопрос утвердительный ответ.

Д. Дербишир «Простая одержимость»

Ну, один из способов – это посмотреть на последнюю цифру суммы: если при сложении 143 и 19 у нас получилось число, оканчивающееся, допустим, на 4, то мы точно где-то ошиблись, так как в одном мы уверены на 100 процентов – правильный ответ обязан заканчиваться двойкой, потому что 3 + 9 = 12.

Каким способом мы могли бы проверить, что не ошиблись при сложении двух чисел?

0

А нам пора двинуться еще немного дальше... и продолжить исследование алгебраической структуры ℕ . со сложением.

Конечной она становится потому,
что сумма, равная 10, отождествляется с нулем.
В результате у нас получается цикл и новое множество, состоящее всего из 10 элементов: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Заметьте, что оно тоже замкнуто относительно сложения (последняя цифра суммы любых двух чисел от 0 до 9 есть число от 0 до 9), в нем по-прежнему есть элемент ноль, прибавление которого к любому элементу множества никак не сказывается на результате, но также появилось и нечто новое - у каждого элемента теперь появился противоположный, т. е. такой, прибавление которого к данному элементу дает в результате ноль! Такая структура носит название группы.

0

Так, на множестве ℕ . довольно естественным образом возникает новая операция «сложения по модулю 10», при которой «суммой» любых двух чисел будет одна из 10 цифр, на которую заканчивается их обычная сумма. Получится некоторая конечная «таблица сложения», в которой принимают участие лишь числа от 0 до 9:

Конечной она становится потому,
что сумма, равная 10, отождествляется с нулем.
В результате у нас получается цикл и новое множество, состоящее всего из 10 элементов: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Заметьте, что оно тоже замкнуто относительно сложения (последняя цифра суммы любых двух чисел от 0 до 9 есть число от 0 до 9), в нем по-прежнему есть элемент ноль, прибавление которого к любому элементу множества никак не сказывается на результате, но также появилось и нечто новое - у каждого элемента теперь появился противоположный, т. е. такой, прибавление которого к данному элементу дает в результате ноль! Такая структура носит название группы.

Итак, на основе множества ℕ

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

Если, скажем, класс

Попробуем составить соответствующую таблицу:

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

то в качестве представителя данного класса, или его «имени», мы можем выбрать не наименьшее положительное число, а наименьшее по абсолютной величине, т. е. −3. Таких представителей класса равноостаточных чисел называют, соответственно, наименьшим положительным и абсолютно наименьшим вычетом. Так, нашу группу по сложению иногда бывает удобно мыслить себе как систему, состоящую из абсолютно наименьших вычетов:

На элементы группы можно смотреть и шире − как на классы чисел, объединенные тем, что они дают один и тот же остаток от деления на 10: в этом смысле элемент 0 − это бесконечное множество натуральных чисел, кратных 10, элемент 1 − это все числа, дающие при делении на 10 остаток 1, и т. д.

Подумайте, как устроено деление в этом кольце? Или по-другому: какие элементы имеют обратные по умножению?

0

На множестве {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} можно рассмотреть еще одну симметрию, если мы
в класс остатков разрешим добавлять и отрицательные числа.

ℤ},

7 = {10k + 7, k

Обратите внимание, что ненулевая часть таблицы умножения любого числа m остатков, в дополнение к осевой симметрии относительно диагонали, которую имела и таблица сложения (с каким свойством сложения и умножения чисел связана эта симметрия?), имеет центральную симметрию. Это связано с тем, что произведение чисел xy ... 1 ≤ x ≤ m, 1 ≤ y ≤ m .. имеет тот же остаток от деления на m, что и (m − x) (m − y).

К. Ф. Гаусс «Труды по теории чисел»

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

Таким образом ℤ распадается (факторизуется) на m непересекающихся подмножеств, которыми, собственно, и исчерпывается. Таким образом некоторые числа отождествляются, образуя эквивалентный класс чисел, дающих один и тот же остаток при делении на m. При этом говорят, что мы факторизовали ℤ по mℤ, и обозначают получившееся множество подмножеств (классов) как ℤ/mℤ.

Теперь, когда мы позволили себе рассматривать все множество ℤ, уместно будет сказать несколько слов об обозначении множества остатков от деления на 10 как ℤ /.. ℤ: оно связано с более общей конструкцией, известной в алгебре как факторизация.

Но не в смысле разложения какого-то числа на простые сомножители, а в более широком – например, «разложения» множества целых чисел ℤ на эквивалентные классы остатков от деления этих чисел на некоторое натуральное число m.

Разложение это выполняется следующим образом: в ℤ мы выбираем некоторое подмножество mℤ целых чисел, кратных m, и строим новые подмножества ℤ, прибавляя к элементам mℤ последовательно все

.

mℤ, 2

mℤ

,…,

причём некоторые подмножества будут совпадать. (Подумайте, какие?)

Мы будем получать подмножества в ℤ вида

10

Говорят, что два целых числа a и b сравнимы по модулю m, если их разность a − b делится на m. И сравнимость чисел a и b по модулю m записывают как

(mod m)

a ≡ b

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

Заметим, что a ≡ b (mod m) если и только если a и b имеют одинаковые остатки от деления на m. Сможете ли вы сами строго доказать, почему это так?

И. М. Виноградов «Основы теории чисел» (Главы 3–5).

А подробный разбор одного из важнейших приложений двух, пожалуй, самых известных теорем этого раздела теории чисел – малой теоремы Ферма и теоремы Эйлера – к криптографии вы найдёте у Эдварда Френкель.

В любом случае дальнейшее знакомство со свойствами сравнений мы предлагаем вам продолжить с помощью вот этой замечательной книги – Виноградов «Основы теории чисел», главы 3-5.

Э. Френкель «Любовь и математика»
(с. 199–200 – в особенности, сноски 6 и 7)

С ее основами вы можете познакомиться
в соответствующем разделе нашей домашней страницы – там вы сможете изучить

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

И. Н. Сергеев, С. Н. Олехник, С. Б. Гашков «Примени математику» (Главы 6-8)

С. Сингх «Великая Теорема Ферма»

n

n

n

Евклид показал, что таких троек бесконечно много (Сергеев и Ко «Примени математику» главы 6-8), а вот для показателей степени n, больших двойки, диофантово уравнение x . + y . = z . вовсе не имеет решений – данный факт носит название Большой теоремы Ферма, а история ее доказательства напоминает настоящий детективный роман – таковым является книжка Саймона Сингха «Великая теорема Ферма», прочитать которую мы вам настоятельно советуем.

2

2

2

В этом смысле теорема Пифагора x ..+ y ..= z ..представляет собой одно из таких уравнений, а тройки целых чисел, для которых равенство выполняется, называют Пифагоровыми тройками.

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

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

Что привело нас прямиком к диофантовым уравнениям, а от них – к Пифагоровым тройкам и Великой теореме Ферма.

Вообще говоря, есть различные способы «генерации» Пифагоровых троек – в их числе установление взаимно-однозначного соответствия между всеми такими тройками и точками с рациональными координатами, лежащими на окружности единичного радиуса. Такое соответствие возникает потому, что если разделить уравнение

то получим в точности уравнение единичной окружности:

где a и b - это рациональные числа:

Подробнее об этом вы сможете прочитать в самом начале вот этой книги:

В. В. Острик, М. А. Цфасман «Алгебраическая геометрия и теория чисел» («Рациональные и эллиптические кривые»)

вывод

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

.

,