Читать онлайн «Теоремы и задачи алгебры, теории чисел и комбинаторики»

В. А. Колосов Теоремы и задачи алгебры, теории чисел и комбинаторики Учебное пособие Москва «Гелиос АРВ» 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, но и связанные с поиском больших простых чисел тесты Миллера — Рабина и Соловэя — Штрассена. Свойства классов вычетов вводятся как средства, необходимые для «взлома» простейших криптосистем и для построения конечных проективных плоскостей. Группы перестановок изучаются в связи с теорией решениия алгебраических уравнений и подсчетом числа многогранников с окрашенными гранями. В связи с этим подходом пришлось делать лакуны в доказательствах некоторых теорем. Все эти случаи оговариваются в тексте. В основном они связаны с дублированием стандартного материала (линейной алгебры, разложением рациональной функции в сумму простейших дробей и т. п. ). Мы не стали занимать место доказательством того, что конечное поле состоит из рп элементов. Вместо этого мы доказали рекуррентную формулу и оценки для числа неприводимых многочленов над полем вычетов, и из существования неприводимого многочлена любой степени вывели существование конечных полей.