Тема 5. теорема о делении с остатком. алгоритм евклида

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

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

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

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

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

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

                                                                  , если .

   Примеры.

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

    .

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

На следующей теореме основан ещё один способ нахождения наибольшего общего делителя.

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

   тогда   .

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

                  ,             ,

                  ,             ,

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

                …………..                ………..

                ,         ,

                .

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

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

Задания для самостоятельного решения

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

Установить, как изменится остаток (при делении с остатком), если делимое и делитель увеличить (или уменьшить) в одно и то же число раз.

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

Доказать, что если делимое ( при делении с остатком) есть произведение нескольких чисел, то остаток от деления этого произведения на некоторое число не изменится, если уменьшить или увеличить один из множителей на число, кратное делителю.

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

Какое число можно прибавить к делимому (при делении с остатком), чтобы частое не изменилось?

Какие числа можно прибавить одновременно к делимому и делителю (при делении с остатком), чтобы частное не изменилось?

При каком условии деление числа А (с остатком) на два последовательных числа а и а+1 дает в частном одно и то же число?