Теорема. Если натуральные числа а, т взаимно просты, то

Следствие. Если р — простое число и , то

Для доказательства утверждения а) достаточно заметить, что . Утверждение б) при следует из а) и следствия 1 теоремы 2, а при очевидно, поскольку в этом случае

.

Заметим, что утверждение а) следствия впервые доказал Ферма, оно называется малой теоремой Ферма. Теорема б была позднее доказана Эйлером и носит название теоремы Эйлера — Ферма. Она находит ши­рокое применение в математике и ее приложениях и, в частности, может оказаться полезной при нахождении остатков от деления степеней чис­ла на заданное число, при решении сравнений с неизвестными и т. д.

Кольцо вычетов

Рассмотрим множество всех классов вычетов по модулю . Класс состоит из всех чисел вида , где t пробегает множество Z, т. е.

Следовательно, классы вычетов по модулю та совпадают со смеж­ными классами кольца Z по его идеалу mZ.

Теорема 1. Определение операций сложения и умножения классов вычетов по формулам

корректно, и множество с этими операциями является коммутативным кольцом с единицей. Это есть факторкольцо кольца Z по его идеалу тZ.

Кольцо Z/rn называют кольцом классов вычетов по модулю т.

Опишем обратимые элементы этого кольца.

Теорема 2. Элемент обратим в кольце Z/m тогда и только тогда, когда класс взаимно прост с т, т. е. (а,т) = 1.

Китайская теорема об остатках

Пусть m - натуральное число, m₁, m₂,..., m_t - взаимно простые натуральные числа, произведение которых больше либо равно m.

Теорема:

Любое число x: 0 <= x <= m может быть однозначно представлено в виде последовательности r(x) = (r1, r2,..., rt), где ri = x(mod mi).

Для любых чисел r1.. rt, таким образом, существует единственное число x(mod m), такое что

x = ri(mod mi), 1 <= i <= t

Более того, любое решение x набора такого сравнений имеет вид

x = r1*e1 +... + rt*et (mod m), где ei = m / mi * ((m/mi)-1 mod mi), 1 <= i <= t.

 

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

Обход в глубину — это обход связного графа (или компоненты связности) по следующим правилам (алгоритм обхода):

1) Рассматриваем вершину Х. Двигаемся в любую другую, ранее непосещенную вершину (если таковая найдется), одновременно запоминая дугу, по которой мы впервые попали в данную вершину;

2) Если из вершины Х нельзя попасть в ранее непосещенную вершину или таковой нет, то возвращаемся в вершину Z, из которой впервые попали в X, и продолжаем обход в глубину из вершины Z.

3) Такой обход графа продолжается до тех пор, пока очередная вершина Х, не совпадет с вершиной Х₀,с которой начался обход графа (компоненты связности).

Обход в ширину — это обход связного графа (или компоненты связности) по следующим правилам (алгоритм обхода):

1) Рассматриваем вершину Х. Ей присваивается метка 0;

2) Всем смежным вершинам с вершиной с меткой 0 поочередно присваиваются метки 1;

3) Всем смежным вершинам с вершинами с меткой 1 поочередно присваиваются метки 2;

4) И т.д. до тех пор, пока не будут помечены все вершины в текущем графе (компоненте связности).

Связный граф

Граф, в котором все вершины связаны.