Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Основную роль во всей арифметике целых чисел играет теорема о делении с остатком.
Теорема 4.1. Для любого целого а и целого существуют и единственные целые q и r, такие что .
Замечание 4.3. Если то q называется неполным частным, а r – остатком от деления a на b.
Замечание 4.2. В частности, если , то и делится на .
Из теоремы 4.1 следует, что при фиксированном целом m > 0 любое целое число а можно представить в одном из следующих видов:
При этом если то будем иметь , если и
, если .
Примеры.
Важным следствием из теоремы о делении с остатком является еще одно свойство делимости.
Теорема 4.4. Разность целых чисел а и b делится на натуральное число m в том и только в том случае, когда числа а и b при делении на m дают одинаковые остатки.
Замечание. Такие числа называют еще равноостаточными, или сравнимыми по модулю m.
На следующей теореме основан ещё один способ нахождения наибольшего общего делителя целых чисел.
Теорема 4.5. Пусть a и b – два целых числа, 0 и , тогда .
Этот способ называется алгоритмом Евклида. Задача нахождения НОД чисел a и b сводится к более простой задаче нахождения НОД b и r, . Если r = 0, то . Если же , то рассуждения повторяем, отправляясь от b и r. В результате получаем цепочку равенств:
, ,
, ,
, , ……………………(**)
………….. ………..
, ,
.
Мы получим убывающую последовательность натуральных чисел
которая не может быть бесконечной. Поэтому существует остаток, равный нулю: пусть . На основании теоремы 4.5 из (**) следует, что .
Число n называется модулем сравнения. Символически сравнимость записывается в виде формулы (сравнения):
Например, 32 и −10 сравнимы по модулю 7, так как оба числа при делении на 7 дают остаток 4:
Эквивалентные формулировки: числа сравнимы по модулю n, если:
Для вышеприведенного примера: 32 и −10 сравнимы по модулю 7, так как их разность делится на 7, и к тому же имеет место представление:
Свойства
Отношение сравнимости по модулю натурального числа обладает следующими свойствами:
В силу того, что отношение сравнимости по модулю обладает этими тремя свойствами, оно является отношением эквивалентности на множестве целых чисел.
Любые два целых числа сравнимы по модулю
Если числа a и b сравнимы по модулю n, и n делится на m, то a и b сравнимы по модулю m.
Для того, чтобы числа a и b были сравнимы по модулю n, каноническое разложение на простые сомножители которого:
необходимо и достаточно, чтобы
Если и , то , где .