Читать онлайн «Дискретная математика. Теория чисел: Учебное пособие»

ÌÈÍÈÑÒÅÐÑÒÂÎ ÎÁÐÀÇÎÂÀÍÈß ÐÎÑÑÈÉÑÊÎÉ ÔÅÄÅÐÀÖÈÈ Ñàíêò-Ïåòåðáóðãñêèé ãîñóäàðñòâåííûé óíèâåðñèòåò àýðîêîñìè÷åñêîãî ïðèáîðîñòðîåíèÿ И. Л. Ерош ДИСКРЕТНАЯ МАТЕМАТИКА ТЕОРИЯ ЧИСЕЛ Учебное пособие Ñàíêò-Ïåòåðáóðã 2001 УДК 512. 54 E 78 ББК 22. 1 Ерош И. Л. Е78 Дискретная математика. Теория чисел: Учеб. пособие/СПбГУАП. СПб. , 2001. 34 c. В учебном пособии кратко изложены основные положения раздела дискретной математики “Теория чисел”. Приведены задачи для самосто- ятельного решения. Перед каждым набором задач приводится разбор при- меров. В заключение приведены примеры использования данного разде- ла при построении различных технических систем. Пособие ориентировано на студентов технических университетов, аспирантов и преподавателей дисциплины “Дискретная математика”. Рецензенты: кафедра радио систем Санкт-Петербургского электротехниче ского университета; кандидат техниче ских наук доцент В. Н. Сасковец Óòâåðæäåíî ðåäàêöèîííî-èçäàòåëüñêèì ñîâåòîì óíèâåðñèòåòà â êà÷åñòâå ó÷åáíîãî ïîñîáèÿ © Санкт-Петербургский государственный университет аэрокосмического приборостроения, 2001 2  Моей дочери Анастасии Ерош посвящаю ВВЕДЕНИЕ Одним из разделов дискретной математики является теория чисел, которая первоначально изучала свойства целых чисел. Целое число яв- ляется одним из древнейших математических понятий, связанных с подсчетом окружающих предметов. Теория чисел возникла из задач арифметики и первоначально оперировала четырьмя арифметическими действиями над натуральными (целыми, положительными) числами. Основными понятиями этой теории являлись простые числа, состав- ные числа, квадратные числа (числа, равные квадрату некоторого другого числа), совершенные числа (числа равные сумме своих дели- телей). В VI веке до н. э. в Древней Греции было известно решение урав- нения x2 + y2 = z2 в целых числах. В III веке до н. э. Евклид в “Началах” обосновал алгоритм нахожде- ния наибольшего общего делителя двух произвольных целых чисел и доказал, что количество простых чисел является бесконечным. Эра- тосфен предложил метод нахождения простых чисел (“Решето Эратос- фена”). Систематизация проблем теории чисел и методов их решений была выполнена в III веке н. э. Диофантом в “Арифметике”. В XVII веке н. э. Ферма исследовал решения многих уравнений в целых числах и высказал гипотезу, что уравнение xn + yn = zn, n>2, x, y, z – целые, не имеет решений (великая теорема Ферма). Ему также принадлежит ут- верждение, что если a и p (p – простое число) взаимно простые числа (наибольший общий делитель этих чисел равен 1), то ap – a делится на p нацело (малая теорема Ферма).