WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 | 4 |
И. Л. Ерош ДИСКРЕТНАЯ МАТЕМАТИКА ТЕОРИЯ ЧИСЕЛ Учебное пособие 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 нацело (малая теорема Ферма). Эйлер доказал великую теорему Ферма при n = 3 и обобщил малую теорему Ферма, введя понятие функции (m) – количества чисел ряда 1, 2, 3, …, m взаимно простых с m, ныне называемую функцией Эйлера от целого m, и показал, что любое число a взаимно простое с m, возведенное в степень (m), при делении на m дает в остатке 1. Проблема нахождения целых положительных остатков при делении одного целого на другое возникла из задач календарных расчетов в Китае (Сунь-цзы, Цинь Цзюшао) и в современном виде формулируется как китайская теорема об остатках.

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

Теория чисел тесно связана с другими разделами дискретной математики: теорией графов, комбинаторикой, теорией конечных автоматов, дискретным спектральным анализом и, конечно, с теорией дискретных групп. Так, множество чисел 0, 1, 2, …, p–1 удовлетворяет аксиомам группы с операцией сложения по модулю p. Если считать p простым числом и исключить из множества 0, то оставшееся множество с операцией умножения по модулю p также образует группу. В этом случае множество чисел 0, 1, 2, …, p–1 с двумя заданными на нем операциями сложения и умножения по модулю p образует числовое поле, которое называется полем Галуа и обозначается GF(p) – сокращение от Galois Field. Галуа показал, что для любого простого p и целого h существует конечное поле с числом элементов равным ph. Такое поле обозначается GF (ph). Оно является для заданных p и h единственным ( с точностью до изоморфизма). В любом поле GF (ph) в качестве подполя содержится поле GF(p). Обычно поля Галуа вида GF (ph) не рассматриваются в теории чисел, однако, логическая связь этих полей с числовыми полями GF (p), похожие свойства полей и тесное переплетение в технических приложениях позволили автору рассмотреть их основные свойства в данном пособии.

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

1. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ 1.1. Делимость целых чисел Что общего между числами множества 9, 16, 23, 30, 37, 44 кроме того, что они все целые Казалось бы, ничего. Однако если ввести операцию деления с остатком и интересоваться только целым положительным остатком от деления чисел этого множества на 7, то окажется, что все они будут иметь одинаковый остаток, равный 2. Эти числа эквивалентны по этому свойству. Тогда приведенную последовательность можно продолжить дальше: 51, 58, 65, 72, 79 … Это множество чисел является бесконечным и счетным, все числа множества объединяет одно общее свойство: при делении на 7 они дают целый положительный остаток 2. Говорят, что эти числа a сравнимы по модулю 7. Такое свойство множества обозначают a 2 mod 7.



Можно рассмотреть другое множество чисел, например, 3, 12, 21, 30, 39, 48,... и убедиться в том, что при делении на число 9, все они дают остаток 3; т.е. общее свойство чисел a этого множества можно записать так:

a 3 mod 9.

Произвольное целое число a единственным образом может быть представлено в виде a = mt + r, где m > 0 – целое положительное число (делитель); t – частное; r – остаток ( 0 r < m).

Так, например, если a = 17, m = 5, то 17 = 5*3 + 2.

В дальнейшем мы будем использовать операцию деления и интересоваться только остатком, не обращая внимание на частное. Так, например, число 16 при делении на 11 дает остаток 5.

Наименьший положительный остаток от деления некоторого числа a на число m обычно называют наименьшим неотрицательным вычетом a по модулю m. Если m делит a нацело, то остаток r = 0. Например, наименьший неотрицательный вычет при делении числа 18 на 6 равен 0.

Пусть имеется два числа a и b. Будем говорить, что они сравнимы по модулю m, если при делении на m они дают одинаковый целый положительный остаток. Например, числа 8 и 15 при делении на 7 имеют одинаковый остаток 1, т. е. они сравнимы по модулю 7. Сравнение чисел будем обозначать так a b mod m.

Сравнению a 0 mod m удовлетворяют все числа a, которые делятся на m нацело или, как говорят, кратные m.

1.2. Свойства сравнений От сравнения a b mod m можно перейти к равенству. Сравнение a b mod m справедливо, если выполняется следующее равенство a = b + m *t, где * – умножение; t – некоторое целое (положительное, отрицательное или 0).

Такая связь между сравнениями и равенствами позволяет распространить понятие сравнения не только на положительные, но и на отрицательные числа. Например, можем записать 12 7 2 –3 –8 –13 … mod 5.

Из связи между сравнениями и равенствами следуют правила эквивалентных преобразований сравнений:

a) Если a b mod m и b c mod m, то a с mod m.

б) Если a b mod m и с d mod m, то a+b с+d mod m. Это правило можно сформулировать и так: сравнения по одинаковому модулю можно почленно складывать.

в) Если a b mod m, то a b+m*t mod m, так как справедливо сравнение m*t 0 mod m, т. е. к любой части сравнения можно прибавить модуль, умноженный на любое целое.

г) Если a b mod m и с – любое целое, взаимно простое с m, то a/c b/c mod m, т. е. обе части сравнения можно разделить на любое целое, если оно взаимно просто с модулем m.

Последнее свойство позволяет распространить понятия сравнения и на дробные числа.

Так, например, если имеем сравнение 1/3 16/15 mod 11, то так как (15, 11)=1, т. е. числа 15 и 11 взаимно просты, то обе части сравнения можно умножить на 15 и получим эквивалентное сравнение:

5 16 mod 11.

1.3. Решение сравнений Из приведенных правил эквивалентных преобразований сравнений следуют общие приемы решения сравнений. Пусть требуется решить сравнение 27 –13* 5 10*X mod относительно неизвестного X. Можно показать, что если в сравнении имеется арифметическое выражение, то любой член его можно заменить остатком от деления на модуль (в общем случае – на любое сравнимое с ним число). Поскольку 27 6 mod 7, 13 –1 mod 7 и 10 3 mod 7, то исходное сравнение можно представить в виде 6 – (–1)*5 3*X mod 7.

Далее вычисляем 11 3*X mod 7, 18 3*X mod 7, 6 X mod 7. Откуда одно из решений сравнения X=6. Общее решение X = 6 + t*7.

Упражнения Найти общие решения следующих сравнений:

а) 8 3X mod 11;

б) 25 15 X mod 17;

в) 3( 24–18)/5 7X mod 19;

г) 8125 – 6 29 5X mod 7;

д) (1824 + 2083) / (216) 233X mod 19;

е) 10112+1258 2X mod11.

1.4. Наименьшее общее кратное и наибольший общий делитель Пусть имеется n целых чисел: a1, a2, a3, …, a. Общим кратным n этих чисел называется целое число, которое делится нацело на каждое из этих чисел. Наименьшее из этих общих кратных называется наименьшим общим кратным чисел a1, a2, a3, …, a и обозначается НОК n (a1, a2, a3, …, a ) или [a1, a2, a3, …, a ].

n n Пусть имеется n целых чисел a1, a2, a3, …, a. Общим делителем этих n чисел называется число, которое нацело делит каждое их этих чисел.

Среди делителей имеется наибольшее число, которое называется наибольшим общим делителем НОД (a1, a2, a3, …, a ) или (a1, a2, a3, …, a ).

n n 1.5. Простые числа. Разложение на простые сомножители.

Каноническая форма числа Число, которое не имеет никаких делителей, кроме 1 и самого себя, называется простым числом. Примеры простых чисел: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, … Любое число N может быть представлено в виде произведения степеней простых чисел (каноническое представление числа). Такое представление единственно (с точностью до перестановки сомножителей).

Так, число 600 = 233152.

Для представления числа N в канонической форме можно использовать следующий алгоритм. Число N делим на наименьшее простое число 2 до тех пор, пока оно делится нацело, затем на 3, на 5 и т. д.

Например, N = 10500.

10500 : 2 = 5250; 5250 : 2 = 2625. Это число больше не делится на нацело. Делим его на 3. 2625 : 3 = 875. Это число на 3 нацело не делится.

Делим его на 5. 875 : 5 = 175. Еще раз делим на 5. 175 : 5 = 35. Еще раз делим на 5. 35 : 5 = 7. Число 7 – простое число, поэтому окончательно имеем в канонической форме: 10500 = 22315371.





1.6. Определение НОК И НОД чисел Для произвольного целого числа a и произвольного целого положительного числа b существуют такие числа t и r, что a = bt + r, где 0 r < b.

Причем такое представление единственное.

Можно показать, что – если b | a ( b делит a нацело), то (a, b) = b и – если a = bt + r, то (a, b) = (b, r).

Для нахождения наибольшего общего делителя двух чисел a и b известен алгоритм Эвклида.

Пусть a b. Рассмотрим следующую последовательность равенств:

a = bt1 + r2 0 < r2 < b.

b = r2t2 + r3 0 < r3 < r2.

r2 = r3t3 + r4 0 < r4 < r3.

........

r = r t + r 0 = r.

n–1 n n n+1 n+Поскольку a b > r2 > r3 > … 0, то алгоритм имеет конечное число шагов. Согласно указанным свойствам (a, b) = (b, r2) = (r2, r3) = … = r n.

Таким образом, наибольший общий делитель чисел a и b равен последнему ненулевому остатку в последовательности равенств, т. е. r.

n А наименьшее общее кратное a и b равно:

[a, b] = ab/(a, b).

Упражнения Используя алгоритм Эвклида, найти НОК и НОД чисел:

а) 575 и 155;

б) 840 и 188650;

в) 4851 и 29106;

г) 975 и 616.

Если два числа N1 и N2 представлены в канонической форме соответственно N1 = p1n p2n2 … psns, N2 = p1m1p2m2… psms, то НОК ( N1, N2) = p1max(n1, m1)p2max(n2, m2)psmax(ns, ms), а НОД ( N1, N2) = p1min(n1, m1)p2min(n2, m2)psmin(ns, ms) Если в каноническом представлении одного из чисел отсутствует какой-либо простой сомножитель, его можно ввести в нулевой степени.

Например, для чисел N1 = 235271 и N2 = 3151112, прежде чем находить НОК и НОД требуется их привести к одинаковой форме, т. е.

сделать так, чтобы в каноническом представлении обоих чисел присутствовали бы одинаковые простые числа в соответствующих степенях, а именно N1 = 23305271110;

N2 = 20315170112.

Тогда НОК (N1, N2) = 23315271112 = 508200;

НОД (N1, N2) = 20305170110 = 5.

Упражнения Найти НОК и НОД для пар чисел:

а) N1 = 440, N2 = 6050;

б) N1 = 234, N2 = 4125;

в) N1 = 66550, N2 = 40131;

г) N1 =388, N2 = 1647.

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

Упражнения Найти НОК и НОД для следующих наборов чисел:

а) N1 = 60, N2 = 350, N3 = 495;

б) N1 = 265, N2 = 104, N3 = 93;

в) N1 = 2100, N2 = 630, N3 = 5880, N4 = 9450;

г) N1 = 700, N2 = 495, N3 = 104;

д) N1 = 103, N2 = 260, N3 = 121.

1.7. Функция Эйлера (m) Функция Эйлера (m) определяется для всех целых чисел m как количество чисел ряда 1, 2, 3, …, m взаимно простых с m. Так, (1) = 1 (по определению), (2) = 1, (3) = 2, (4) = 2, (5) = 4 и т. д. Легко показать, что для m = p – простых чисел (p) = p –1. Для m = pn функция Эйлера (pn) = pn–1(p –1). Для произвольного числа m, представленного в канонической форме, m = p1n1p2n2…psns функция Эйлера определяется следующим образом:

(m) = m(1–1/p1)(1–1/p2)…(1–1/ps).

Например, (11) = 10; (9) = 6; (18) = 6.

Упражнения Вычислить функцию Эйлера (m) для чисел m = 7, 12, 15, 17, 23, 24, 25, 28, 37, 54, 64.

1.8. Сравнимость чисел и классы вычетов Выпишем все числа от 1 до 8 и вычеркнем все числа не взаимно простые с 8. Количество оставшихся чисел равно (m=8) = 4, а сами эти числа: (1, 3, 5, 7). Множество этих чисел обладает свойством замкнутости относительно операции умножения по модулю m = 8. Действительно, перемножая любые пары чисел из множества (1, 3, 5, 7) и находя наименьший положительный остаток по модулю m = 8, будем получать всегда одно из этих же чисел. Каждое их этих чисел порождает бесконечный счетный класс чисел:

1+8*t; 3+8*t; 5+8*t; 7+8*t, где t – любое целое.

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

при любых целых t произведение представителей классов (1+8*t; 3+8*t;

5+8*t; 7+8*t) дает в результате представителя одного из этих же классов.

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

Упражнения Постройте абелевы группы классов, порождаемые числами 10, 12, 15, 18, 21, 24, 25, 27, 28.

1.9. Теоремы Ферма и Эйлера а) Теорема Ферма.

Если p – простое число и (a, p)=1, то a p –1 1 mod p.

Пусть p = 23, a = 18. Очевидно, что (23, 18) = 1, следовательно, 1822 1 mod 23. Проверить этот результат несложно. Для этого заметим, что 18 –5 mod 23, поэтому можно написать эквивалентное сравнение (–5)22 1 mod 23 или 522 1 mod 23.

Последнее сравнение можно представить в виде (52)11 1 mod 23 и так как 25 2 mod 23, то 211 1 mod 23.

Полученное сравнение элементарно проверяется : 2048 1 mod 23.

б) Теорема Эйлера.

Если m >1 и (a, m)=1, то a(m) 1 mod m. Эта теорема обобщает теорему Ферма, так как при m = p, (m = p) = p –1.

Пусть m = 18, a = 5. Очевидно, что (5, 18) = 1.

Функция Эйлера (m = 18) = 6. Поэтому 56 1 mod 18. Это сравнение проверяется достаточно просто:

52 7 mod 18, следовательно, ((52))3 73 = 343 1 mod 18.

Упражнения На основании теорем Ферма и Эйлера доказать справедливость сравнений:

236 336 … 3636 1 mod 37;

2100 3100 … 100100 1 mod 101;

28 48 78 88 118 138 148 1 mod 15.

Pages:     || 2 | 3 | 4 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.