Каталог@Mail.ru - каталог ресурсов интернет HitMeter - счетчик посетителей сайта, бесплатная статистика

Наибольший общий делитель: понятия, алгоритм нахождения

1. Что такое наибольший общий делитель

Наибольший общий делитель натуральных чисел n, m - наибольшее натуральное число y, на которое n и m делятся без остатка.

Пример: n = 15, m = 9, тогда НОД(n, m) = 3.

Если НОД(n, m) = 1, то n, m - взаимно простые числа.

Пример: 15 и 8 - взаимно простые числа.

На одной из страниц нашего сайта был рассмотрен вопрос, как подобрать взаимно простые числа.

2. Свойства наибольшего общего делителя

1. НОД(n, m) <= min(n, m), где min возвращает наименьший из двух своих аргументов.

Данное свойство не нуждается в особых комментариях.

2. Если n, m - чётные, то НОД(n, m) = 2НОД(n/2, m/2).

В данном случае n и m оба делятся на 2, то есть их НОД имеет вид 2q, где q - натуральное число. Это значит, что n/2 и m/2 оба делятся на q. Если бы m/2 и n/2 оба делились на kq, где k > 1 - натуральное число, то n и m делились бы на 2kq, то есть число 2q не могло быть их наибольшим общим делителем, то есть у нас выходит противоречие. В итоге свойство доказано.

3. Если n кратно 2, m - не кратно 2, то НОД(n, m) = НОД(n/2, m).

Допустим, что это неверно, и НОД уменьшился вдвое при делении n на двойку. Так как он уменьшился вдвое, НОД(n, m) был чётным числом. Но ведь нечётное число m не может иметь чётных делителей. Стало быть, n и m не имеют общих чётных делителей. Это значит, что НОД(n, m) не может быть чётным числом, то есть получили противоречие при попытке предположить, что свойство 3 неверно.

4. Если n, m - нечётные, n > m, то НОД(n, m) = НОД((n-m)/2, m).

Попробуем это доказать. Допустим, НОД(n, m) = q, тогда n = pq, m = kq, где k и p - взаимно простые числа. (n - m)/2 = q(p-k)/2, при этом p и k - нечётные, тогда выходит, что (p-k)/2 - нормальное натуральное, а не дробное число, так как (p - k) - чётное число.

Нам нужно доказать, что (p - k) / 2 и k - взаимно простые числа. (p - k) - чётное, k - нет, пользуемся свойством 2. Теперь нужно доказать, что (p - k) и k - взаимно простые. Пусть у k есть делитель x > 1 (k = fx, где f - натуральное). Мы знаем, что p и k - взаимно простые числа, и нагло этим пользуемся: p = gx + h, где g - натуральное, h > 0 - остаток от деления, потому p - k = gx + h - fx = (g - f)x + h, то есть (p - k) не делится на x. То есть p и k не имеют общих делителей, кроме 1.

Итак, (p-k)/2 и k - взаимно простые числа, в итоге получаем, что (n-m)/2 и m делятся на q, но не делятся одновременно на числа вида bq, где b > 1 - натуральное число.

5. Пусть p, k - взаимно простые числа, a - целое число, такое, что p+ak > 0. Тогда p+ak, k - взаимно простые числа.

Предположим, что p+ak, k имеют наибольший общий делитель x > 1. Тогда p + ak = fx, k = gx, где f, g - натуральные числа. Далее: p = fx - ak = fx - agx = (f - ag)x, то есть p должно делиться на x, чего у нас нет. Противоречие.

3. Бинарный алгоритм для определения наибольшего общего делителя

Требуется найти НОД(n, m).

1. Граничные условия: НОД(0, m) = m, НОД(n, 0) = n, НОД(n, n) = n, НОД(1, m) = 1, НОД(n, 1) = 1.
2. Рекуррентные соотношения (рекурсия):
Если n, m - чётные, НОД(n, m) = 2НОД(n/2, m/2).
Если n чётное, m нечётное, НОД(n, m) = НОД(n/2, m).
Если m чётное, n нечётное, НОД(n, m) = НОД(n, m/2).
При нечётных n и m: если n > m, то НОД(n, m) = НОД((n - m) / 2, m); если m > n, НОД(n, m) = НОД(n, (m - n)/2).

В данных соотношениях следует умножение, деление, проверку на чётность заменить битовыми операциями. Например, вместо n / 2 поставить n >> 1 (битовый сдвиг вправо на единицу). Ради применения таких - относительно быстрых - операций и был разработан данный алгоритм, опубликованный Д. Стайном в 1967 г.

4. Халявный исходник для определения наибольшего общего делителя

Содрать исходник на C++

Реализован бинарный алгоритм Стайна, в коде используются только битовые операции, никаких умножений, делений, остатков от деления. И при том издевательски короткий код)))))))))))))))))))))))))))))))))))))))))))))

copyright © Исканцев Н.В., 2012

К математическому разделу
На главную
X