Уроки математики / Статья / Теорема о делении с остатком. Еще один способ нахождения НОД.

Теорема о делении с остатком. Еще один способ нахождения НОД.

Теорема о делении с остатком. Еще один способ нахождения НОД


Основную роль во всей арифметике целых чисел играет теорема о делении с остатком.

Теорема 4.1. Для любого целого а и целого существуют и единственные целые q и r, такие что .

Замечание 4.2. В частности, если , то и делится на .

Замечание 4.3. Если то q называется неполным частным, а r – остатком от деления a на b.

Из Т.4.1. следует, что при фиксированном целом m>0 любое целое число а можно представить в одном из следующих видов:



При этом если то будем иметь , если и

, если .

Примеры.


  1. Любое целое число можно представить в виде или


.


  1. Любое целое число можно представить в виде или или .


Теорема 4.7. Пусть a и b – два целых числа, 0 и ,

тогда .

Этот способ называется алгоритмом Евклида. Задача нахождения НОД чисел a и b сводится к более простой задаче нахождения НОД b и r, . Если r = 0, то . Если же , то рассуждения повторяем, отправляясь от b и r. В результате получаем цепочку равенств:

, ,

, ,

, , ……………………(**)

………….. ………..

, ,

.

Мы получим убывающую последовательность натуральных чисел



которая не может быть бесконечной. Поэтому существует остаток, равный нулю: пусть . На основании Т.4.7. из (**) следует, что

Автор
Дата добавления 07.04.2017
Раздел Начальная
Подраздел Статья
Просмотров803
Номер материала 3592
Включите уведомления прямо сейчас и мы сразу сообщим Вам о важных новостях. Не волнуйтесь, мы будем отправлять только самое главное.