Вычисление НОД. Алгоритм Евклида

ГЛАВА 3. ДЕЛИМОСТЬ ЧИСЕЛ. ДЕЛЕНИЕ С ОСТАТКОМ. НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ.

 

Делимость чисел

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

    Определение 1.1. Пусть  и  – целые числа. Говорят, что число  делится на число , если найдется такое целое число , что . При этом число  называют делимым, число  – делителем, а число – частным.

Факт делимости числа  на число  обозначают . Также говорят, что  кратно .

    Примеры. 1) 65 13, так как ;

                        2) 0 3, так как ;

                        3) 5, так как .

 

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

                        .

Если , то . Значит, в случае, когда делитель отличен от нуля, частное единственно.

Если , то, очевидно, , и равенство  выполняется для любого значения .Таким образом, на  делится только , а частное от такого деления неопределенно (может быть любым числом).

В дальнейшем, говоря о делении, всегда будем предполагать, что делитель отличен от 0.

 

Свойства делимости

 

1. Если , то (– ); (– ) ; (– ) (– ).

Доказательство. Пусть , это значит, что существует такое целое число , что . Тогда , причем число  также является целым. Следовательно, по определению делимости (– ). Остальные утверждения доказываются аналогично.

2. Если  и , то .

Доказательство. , где ; , где . Тогда . Число  – целое, значит, .

Следствие. Из свойств 1 и 2 непосредственно следует, что если  и , то .

3. Если  и , то .

Доказательство. , где . Умножим обе части последнего равенства на , получим . Число – целое, значит, .

4. Если  и  не делится на , то  не делится на .

Доказательство. Предположим, что данное утверждение неверно: . Это значит, что , где . Тогда . Но , где . Следовательно, . Поскольку , получим, что , что противоречит условию. Полученное противоречие доказывает, что сделанное нами предположение неверно.

5. Если  и , то .

Доказательство. , где , причем . Тогда . Но , значит .

Следствие 1. Если , то либо , либо .

Доказательство. Если , то по свойству 5 справедливо неравенство . При этом  – целое число, отличное от 0. Следовательно, , а это и значит, что либо , либо .

Следствие 2. Если  и , то либо , либо .

Доказательство. Если  и , то по свойству 5 справедливы неравенства  и . Одновременное выполнение этих неравенств может быть только в случае, когда , что и означает, что либо , либо .

Отметим, что отношение делимости является бинарным отношением на множестве . Рассмотрим его свойства делимости как бинарного отношения.

1. Рефлексивность. Очевидно, что . Значит, отношение делимости рефлексивно.

2. Проверим, обладает ли отношение делимости каким-либо из свойств симметричности, антисимметричности или асимметричности. По следствию 2 к свойству 5, если  и , то либо , либо . Следовательно, ни одним из перечисленных свойств данное бинарное отношение не обладает.

 Заметим, что если рассмотреть отношение делимости на множестве натуральных чисел N, то окажется, что это отношение обладает свойством антисимметричности. Действительно, в этом случае следствие 2 к свойству 5 примет вид: если  и , то  (поскольку на множестве N равенство невыполнимо).

3. Транзитивность отношения делимости означает, что если  и , то . Докажем, что отношение делимости транзитивно. Действительно,

, где ;

, где .

Следовательно, , при этом, очевидно, , а это и означает, что .

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

 

Деление с остатком

Определение 2.1. Пусть  и  – целые числа. Разделить число  на число  с остатком, значит найти такие целые числа  и , что выполняются условия:

1)

2) .

При этом  называется неполным частным, а – остатком от деления  на .

    Примеры. 1) Разделить 5 на 3 с остатком. В соответствии с определением представим число 5 в виде: 5=3 1+2. Здесь . Условие 2 из определения, очевидно, выполняется.

    2) Разделить (–5) на 3 с остатком: (–5)=3 (–2)+1. Здесь ; .

    3) Разделить 5 на (–3) с остатком: 5=(–3) (–1)+2. Здесь ; .

    4) Разделить (–5) на (–3) с остатком: (–5)=(–3) 2+1. Здесь ; .

        

 

Теорема 2.1. Пусть  и  – целые числа, причем . Число  всегда можно разделить на число  с остатком, причем единственным образом.

    Доказательство. Рассмотрим случай, когда ,

1) Пусть . Рассмотрим последовательность чисел: … Поскольку , начиная с некоторого члена этой последовательности, все члены будут отрицательными. Пусть последним из неотрицательных членов будет число . Положим . Тогда , где . Докажем, что . Запишем это неравенство в виде . Если бы это неравенство не выполнялось, то . Последние неравенство противоречит тому, что является последним неотрицательным числом в последовательности. Таким образом мы доказали, что число  делится на с остатком.

2) Пусть . Рассмотрим последовательность чисел: … Поскольку , начиная с некоторого члена этой последовательности, все члены будут положительными. Пусть – первое неотрицательное число в этой последовательности. Положим . Тогда , где . Докажем, что . Запишем это неравенство в виде . Предположим, что неравенство не выполняется, тогда . Но – первое неотрицательное число в последовательности. Полученное противоречие доказывает, что сделанное нами предположение неверно. Положим , тогда .

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

 Случай, когда , рассматривается аналогично.

3) Докажем, что при делении одного целого числа на другое неполное частное и остаток определяются единственным образом. Пусть .

Предположим, что  и , где  и . Тогда . Поскольку , из последнего равенства следует, что . По свойству 5 делимости чисел, если , то , что невозможно в силу условий  и . Следовательно, , а, значит, и . Случай, когда , рассматривается аналогично.

 

 

Наибольший общий делитель

Определение 3.1. Рассмотрим  целых чисел  и целое число , причем . Число  называется общим делителем чисел , если каждое из этих чисел делится на : , ,…, .

Определение 3.2. Рассмотрим  целых чисел  и целое число . Число  называется наибольшим общим делителем чисел (НОД) чисел , если

1) является общим делителем чисел ,

2) делится на любой из общих делителей чисел .

НОД чисел  обозначают .

    Определение 3.3. Если , то числа  называются взаимно простыми.

        

                  Свойства НОД

 

    Теорема 3.1. НОД чисел  определен однозначно с точностью до знака, т. е., если числа  и  – наибольшие общие делители чисел , то либо , либо .

    Доказательство. Из определения НОД следует, что  и , поскольку оба этих числа являются общими делителями чисел . Тогда по следствию 2 к свойству 5 делимости чисел либо , либо .

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

    Теорема 3.2. Пусть (т. е. число  является наибольшим общим делителем чисел ). Тогда число является наибольшим по величине общим делителем этих чисел.

Доказательство. Пусть  – общий делитель чисел . Тогда из определения НОД следует, что . По свойству 5 делимости чисел . Мы условились считать, что НОД чисел положителен, следовательно, . Учитывая, что , получим требуемое утверждение.

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

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

Достаточность. Пусть , где . Докажем, что . Из условия утверждения следует, что  и , следовательно,  – делитель чисел  и .

Предположим, что – не является наибольшим общим делителем чисел  и . Пусть . Тогда . Это значит, что , где  – целое число, причем . Из определения НОД получим, что . Тогда . Из единственности частного следует, что . Значит, числа  и  не являются взаимно простыми, что противоречит сделанному нами предположению. Полученное противоречие доказывает справедливость утверждения.

 

Вычисление НОД. Алгоритм Евклида

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

Лемма 1. Если , то .

Доказательство. Очевидно, что – общий делитель чисел  и , поскольку  и . Пусть – общий делитель чисел  и , тогда . Значит,  – наибольший общий делитель чисел  и  по определению.

 

Лемма 2. Пусть , причем числа  и  отличны от 0 и . Тогда

Доказательство. Пусть множество общих делителей чисел  и , а  множество общих делителей чисел  и . Докажем, что .

Пусть , это значит, что  и . Тогда по свойству делимости . Тогда, , следовательно, . Аналогично докажем, что . Из определения равенства двух множеств получим, что .

Если два числовых множества совпадают, то совпадают их наибольшие по величине элементы, что и доказывает лемму.

 

Сформулируем теперь алгоритм Евклида.

Рассмотрим два целых числа  и . Пусть  Требуется найти наибольший общий делитель чисел  и .

Шаг 1. Разделим  на . Если , то по лемме 1 получим, что .

Если число  не делится на , то , где . Тогда по лемме 2

Шаг 2. Разделим  на . Если , то  (по лемме 1). Тогда .

Если  не делится на , то , где . Тогда по лемме 2 , а значит, справедливо и

Продолжая процесс деления, получим последовательность остатков – убывающую последовательность целых неотрицательных чисел, вычисляемых по следующим рекуррентным формулам: .

 Поскольку такая последовательность не может иметь бесконечно много членов, на некотором шаге очередной остаток окажется равным нулю. Тогда последний, отличный от нуля остаток и есть НОД чисел  и .

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

Далее, разделим  на , получим , при этом .  Продолжим процесс деления:

, ;

, ;

, ;

, .

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

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

Теорема 4.1. (линейное представление НОД )

      Рассмотрим два целых числа  и . Пусть , . Тогда найдутся такие целые числа  и , что .

Доказательство. Докажем, что каждый из остатков , полученных в процессе выполнения алгоритма Евклида, можно представить в виде линейной комбинации чисел  и  с целыми коэффициентами. Тогда это утверждение будет справедливо в частности и для последнего, отличного от  остатка, равного . Будем доказывать это утверждение методом математической индукции.

База индукции.

Пусть . Имеем , тогда . Получили, что остаток  можно представить в виде линейной комбинации чисел  и  с целыми коэффициентами   и .

Индукционный переход.

Пусть утверждение справедливо для всех натуральных чисел , не превосходящих : , при . Докажем, что это утверждение справедливо также для .

Из алгоритма Евклида следует, что

.

По индукционному предположению

и . 

Следовательно, .

Положим  и . Тогда , что и требовалось установить.

Пример. В предыдущем примере был найден НОД чисел  и  : . Найдем его линейное представление:

Итак, получили, что , т. е. представили НОД чисел  и  в виде их линейной комбинации с целыми коэффициентами.

Взаимно простые числа

Определение 5.1. Целые числа  называются взаимно простыми, если их НОД равен :

Примеры.

1. Числа  и  – взаимно простые.

2. Числа  и  – не взаимно простые, так как .

Следующая теорема устанавливает необходимое и достаточное условие взаимной простоты чисел.

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

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

2. Достаточность. Пусть справедливо утверждение , где  и  – целые числа. Докажем, что . Предположим, что числа  и  не являются взаимно простыми: , причем . Тогда  и , и по свойству делимости . Значит, , следовательно, . Полученное противоречие доказывает, что сделанное нами предположение неверно, и, тем самым, справедливо .

Следствие 1. Если числа  и  взаимно просты, причем  и , то числа  и  также взаимно просты.

Доказательство. По теореме из взаимной простоты чисел  и  следует, что найдутся такие целые числа  и , что . Из определения делимости , , где  и   – целые числа. Тогда 

, а, значит, числа  и  взаимно просты.

Следствие 2. Рассмотрим целые числа ,  и . Если  и , то .

Доказательство. По теореме условие  можно записать в

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

             .

Поскольку – целое число, последнее равенство означает, что .

 

---

Дата добавления: 2021-03-18; просмотров: 174; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!