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

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

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

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

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

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

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

                                                                  , если .

   Примеры.

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

    .

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

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

   тогда   .

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

                  ,             ,

                  ,             ,

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

                …………..                ………..

                ,         ,

                .

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

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

Контрольные вопросы

4.1. Сформулировать теорему о делении с остатком.

4.2. Может ли остаток от деления целого числа быть отрицательным?

4.3. Чему равен остаток от деления целого положительного числа а на число b, если ?

4.4. Какие остатки могут получаться при делении целого числа на положительное число m?

4.5. Могут ли все натуральные числа a, b, c, d оказаться нечетными, если с – частное отделения а на b, а d – остаток от этого деления?