В. А. Колосов
Теоремы и задачи
алгебры,
теории чисел
и комбинаторики
Учебное пособие
Москва
«Гелиос АРВ»
2001
УДК 512. 8
ББК 22. 14+22,19
К 26
Колосов В. А,
К 26 Теоремы и задачи алгебры, теории чисел и
комбинаторики. — М. : Гелиос АРВ, 2001. — 256 с. ISBN 5-85438-021-8
Учебное пособие предлагает введение в теорию чисел и
комбинаторику с позиций конкретной математики. Изложены также
классические разделы алгебры — теория решения уравнений и исключения
неизвестных. Для студентов, специализирующихся по математике и
информатике. ББК 22. 14+22. 19
Издание выпущено в авторской редакции. Учебное пособие
Вадим Александрович Колосов
ТЕОРЕМЫ И ЗАДАЧИ АЛГЕБРЫ, ТЕОРИИ ЧИСЕЛ И КОМБИНАТОРИКИ
Оригинал-макет подготовлен в пакете LATgX2e. Корректор £. Н. Клитина
Лицензия ЛР № 066255 от 29 декабря 1998 г. Издательство «Гелиос АРВ». 104140» Москва, Верхняя Красносельская ул. , 16. Формат 60x84/16. Печать офсетная. Бумага офсетная. Объем 16 п. л. Тираж 3000экз. Зак. № 1548.
Отпечатано с готовых диапозитивов в РГУП «Чебоксарская типография №1».
428019, г. Чебоксары, пр. И. Яковлева, 15. ©Колосов В. Α. , 2001
ISBN 5-85438-021-8 О Оформление. Авилкин С. Η. , 2001
3
Предисловие
В этой книге дается введение в комбинаторику и теорию чисел. Она
представляет собой начальный курс для студентов — математиков и ин-
форматиков, решивших специализироваться в этих областях или
использовать их в работе. Ныне набирает силу тенденция повышения роли
конкретной математики, а принятый здесь элементарный подход находится
в русле этой тенденции. Главное место в нашей книге играют примеры и
задачи, а не теории и аксиоматика. Для понимания основной части книги
не требуется знаний, выходящих за рамки школьной программы. Главными условиями в отборе материала для нас была его
нетривиальность и полезность для приложений. Именно поэтому большая часть
теорем в этой книге непосредственно связана с разбираемыми вместе с
ними задачами. Например, теорему Эйлера из арифметики
иллюстрирует не только система шифрования RSA, но и связанные с поиском
больших простых чисел тесты Миллера — Рабина и Соловэя — Штрассена. Свойства классов вычетов вводятся как средства, необходимые для
«взлома» простейших криптосистем и для построения конечных проективных
плоскостей. Группы перестановок изучаются в связи с теорией решениия
алгебраических уравнений и подсчетом числа многогранников с
окрашенными гранями. В связи с этим подходом пришлось делать лакуны в доказательствах
некоторых теорем. Все эти случаи оговариваются в тексте. В основном
они связаны с дублированием стандартного материала (линейной
алгебры, разложением рациональной функции в сумму простейших дробей и
т. п. ). Мы не стали занимать место доказательством того, что конечное
поле состоит из рп элементов. Вместо этого мы доказали рекуррентную
формулу и оценки для числа неприводимых многочленов над полем
вычетов, и из существования неприводимого многочлена любой степени вывели
существование конечных полей.