Определение наибольшего общего делителя




Лекция 8. Простые числа

 

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

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

n = p1e1 * p2e2 *... * pkek, (8.1)

где p1, p2, …, pk – простые сомножители;

e1, e2, …, ek – количество (степени) простых сомножителей.

Например, n = 600 = 23 * 31 * 52.

Теорема Евклида – простых чисел бесконечно много («Начала», книга IX, утверждение 20).

Возьмем ряд последовательных простых чисел (например, {2, 3, 5}) и перемножим их:

2 * 3 * 5 = 30.

Добавим к результату единицу:

2 * 3 * 5 + 1 = 30 + 1 = 31.

Если разделить 31 на любое простое число из этого ряда (2, 3 или 5), то в остатке получится 1:

31 mod 2 = 1,

31 mod 3 = 1,

31 mod 5 = 1.

Это означает, что число 31 не делится на числа ряда. Такие рассуждения справедливы и в общем случае: если взять ряд последовательных простых чисел, перемножить их и добавить единицу, то полученное число не будет делиться ни на одно из исходных простых чисел. Число 31 тоже простое число, но его нет в первоначальном списке, который, следовательно, является неполным.

Возьмем следующий ряд чисел в качестве примера - {2, 3, 5, 7, 11, 13}, перемножим их и добавим единицу:

2 * 3 * 5 * 7 * 11 * 13 + 1 = 30 030 + 1 = 30 031,

Результат не является простым числом, так как может быть разложен в произведение двух других чисел:

30 031 = 59 * 509,

Согласно основной теоремы арифметики любое натуральное число может быть единственным образом разложено в произведение простых множителей. В случае с числом 30 031, которое является составным числом, ясно, что для его разложения в произведение простых множителей чисел в списке {2, 3, 5, 7, 11, 13} будет недостаточно, т.е. этот список неполон.

Следствием теоремы Евклида является утверждение: каким бы ни был первоначальный ряд простых чисел, при их перемножении и добавлении единицы получается новое число одного из двух типов:

1. простое число, которого нет в списке;

2. составное число, при разложении которого на простые множители получаются простые числа, не входящие в список.

Таким образом, первоначальный ряд простых чисел всегда является неполным, если он не является бесконечно длинным.

 

Определение наибольшего общего делителя

Наибольшим общим делителем (НОД) для двух целых чисел m и n называется наибольший из их общих делителей (например, для чисел 70 и 105 НОД равен 35). НОД существует и однозначно определён, если хотя бы одно из чисел m или n отлично от нуля. Возможные обозначения наибольшего общего делителя чисел m и n:

- НОД(m, n);

- gcd(m, n) (англ. Greatest Common Divisor).

Наиболее известным способом определения НОД является алгоритм Евклида. Этот алгоритм не был открыт Евклидом, т.к. упоминание о нём имеется уже в «Топике» Аристотеля. В «Началах» Евклида он описан дважды - в VII книге для нахождения НОД двух натуральных чисел и в X книге для нахождения наибольшей общей меры двух однородных величин.

Суть алгоритма заключается в последовательном делении большего числа n на меньшее m, до тех пор, пока остаток от деления r не станет равным 0. При этом после каждого деления n присваивается текущее значение m, а m – остаток от деления r.

Описание алгоритма (при n ≥ m).

1. Если m = 0, то завершить работу, т.к. n является НОД.

2. r = n mod m, n = m, m = r и перейти к шагу 1.

Пример. n = 1071, m = 462.

Таблица 8.1. Таблица итераций

Результат – НОД(1071, 462) = 21.

Существует более мощный алгоритм определения НОД – расширенный алгоритм Евклида. Несмотря на то, что он медленнее, данный алгоритм помимо НОД позволяет найти два таких числа α и β, что

α n + β m = НОД. (8.2)

Данное выражение называется соотношением Безу.

Суть расширенного алгоритма аналогична стандартному – последовательное деление большего числа n на меньшее m, до тех пор, пока остаток от деления r не станет равным 0. При этом на каждой итерации дополнительно вычисляются:

- целая часть qi от деления ni на mi;

- αi = αi-2 – qi αi-1;

- βi = βi-2 – qi βi-1.

Для первой итерации принимаются α-1 = 1, α0 = 0, β-1 = 0, β0 = 1. Итоговые числа α и β равны α = αk-2, β = βk-2.

Описание алгоритма (при n ≥ m).

1. α-1 = 1, α0 = 0, β-1 = 0, β0 = 1, i = 1.

2. Если m = 0, то завершить работу, т.к. n является НОД, α = αk-2, β = βk-2.

3. r = n mod m, n = m, m = r, qi = ni div mi, αi = αi-2 – qi αi-1, βi = βi-2 – qi βi-1, i = i + 1 и перейти к шагу 2.

Пример. n = 1071, m = 462.

Таблица 8.2. Таблица итераций

 

Результат – НОД(1071, 462) = 21, α = -3, β = 7 → (-3) * 1071 + 7 * 462 = 21.

Расширенный алгоритм Евклида позволяет найти обратное (мультипликативно обратное) число по модулю.

Пусть даны модуль n и число m. Требуется обратное число m-1, такое, что

(m m-1) mod n = 1. (8.3)

Приведем следующее соотношение Безу

-α n + β m = 1. (8.4)

Это равенство означает, что для некоторого целого α имеет место равенство β m - α n = 1. Значит, мы можем вычислить m-1 (= β) с помощью расширенного алгоритма Евклида. При этом значение переменной α нас не интересует. Если число m-1 = β получается отрицательным, то нужно прибавить к нему n.

Пример. n = 97, m = 30.

Таблица 8.3. Таблица итераций

Т.к. m-1 – отрицательное число, то добавляем к нему n → m-1 = -42 + 97 = 55. Проверяем (m m-1) mod n = (30 * 55) mod 97 = 1.

 



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-04-27 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: