Алгоритм Евклида (нахождение наибольшего общего делителя)

Алгоритм Евклида – это алгоритм нахождения наибольшего общего делителя (НОД) пары целых чисел. Наибольший общий делитель (НОД) – это число, которое делит без остатка два числа и делится само без остатка на любой другой делитель данных двух чисел. Проще говоря, это самое большое число, на которое можно без остатка разделить два числа, для которых ищется НОД.

Описание алгоритма нахождения нод делением

1. Большее число делим на меньшее.

2. Если делится без остатка, то меньшее число и есть НОД (следует выйти из цикла).

3. Если есть остаток, то большее число заменяем на остаток от деления.

4. Переходим к пункту 1.

Пример: Найти НОД для 30 и 18. 30/18 = 1 (остаток 12) 18/12 = 1 (остаток 6) 12/6 = 2 (остаток 0). Конец: НОД – это делитель. НОД (30, 18) = 6

Примечание к коду. В цикле в a или b записывается остаток от деления. Когда остатка нет (мы не знаем в а он или b, поэтому проверяем оба условия), то цикл завершается. В конце выводится сумма a и b, т.к. мы не знаем, в какой переменной записан НОД, а в одной из них в любом случае 0, который на результат суммы никак не влияет.

Описание алгоритма нахождения нод вычитанием

1. Из большего числа вычитаем меньшее.

2. Если получается 0, то значит, что числа равны друг другу и являются НОД (следует выйти из цикла).

3. Если результат вычитания не равен 0, то большее число заменяем на результат вычитания.

4. Переходим к пункту 1.

Пример: Найти НОД для 30 и 18. 30 - 18 = 12 18 - 12 = 6 12 - 6 = 6 6 – 6 = 0 Конец: НОД – это уменьшаемое или вычитаемое. НОД (30, 18) = 6

Малая теорема Ферма. Если   – простое число и   – целое число, не делящееся на  , то  делится на  , то есть Два целых числа   и   называются сравнимы по модулю натурального числа  , если при делении на   они дают одинаковые остатки; или если их разность делится на  . Записывается это следующим образом

  

Определение. Кодом Прюфера длины n – 2 называется последовательность из чисел от 1 до n с повторениями.

Лемма. Количество кодов Прюфера длины n – 2 равно n^n-2.

Теорема. Существует взаимно однозначное соответствие между остовными деревьями для графа из n вершин и кодами Прюфера длины n – 2. По каждому дереву с n вершинами можно построить код Прюфера длины n – 2 и наоборот.

Следствие. Количество пронумерованых деревьев из n вершин равно n^n-2.

Алгоритм построения кода Прюфера по дереву

Вход: дерево с n вершинами.

Выход: код Прюфера длины n – 2.

Повторить n – 2 раза

Выбрать вершину v – лист дерева с наименьшим номером;

Добавить номер единственного соседа v в последовательность кода Прюфера;

Удалить вершину v из дерева;

 

Пример 1. Построение всех кодов Прюфера длины 2. Для этого следует рассмотреть все возможные деревья из 4 вершин. Под каждым деревом приведен соответствующий код.

 

 

Пример 2. Построить код Прюфера по дереву:

 

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

[Править]Примеры:

,  , ,  , ,  .

[Править]Свойства функции Эйлера

• 1. Доказательство:  , p — простое,  .

  • Логически понятно, если строго, то выводится из 2 свойства.

• 2. Пусть   — каноническое разложение числа a, тогда

.

• • Доказательство: Пусть   пробегает числа  , положим   — НОД. Тогда   есть число значений  , равных единице. Возьмем функцию, которая равна единице, если  , и равна нулю в остальных случаях. Вот такая функция :  , где   — функция Мебиуса. Отсюда  . Поскольку справа сумма в скобках берется по всем делителям d числа  , то d делит x и a . Значит в первой сумме справа в суммировании участвуют только те x , которые кратны d . Таких x среди чисел   ровно   штук. Получается, что  .

• 3. Функция Эйлера является мультипликативной  .

  • Вытекает из первого свойства.