Сравнения, система вычетов, решение линейных систем по модулю — различия между версиями
Bochkarev (обсуждение | вклад) |
Bochkarev (обсуждение | вклад) (→Свойства сравнений) |
||
Строка 25: | Строка 25: | ||
*5. Обе части сравнения можно умножить на одно и тоже число. | *5. Обе части сравнения можно умножить на одно и тоже число. | ||
+ | ** Действительно, из <tex>a \equiv b(mod \text{ } m)</tex>, следует <tex> a = b+mt, ak =bk +mkt <tex>, и, следовательно, <tex>ak \equiv bk(mod \text{ } mk)</tex>. | ||
+ | |||
*6. Обе части сравнения и модуль можно разделить на их общий делитель. | *6. Обе части сравнения и модуль можно разделить на их общий делитель. | ||
*7. Если сравнение <tex>a\equiv b</tex> имеет место по нескольким модулям, то оно имеет место и по модулю равному [[Наименьшее общее кратное|НОК]] этих модулей. | *7. Если сравнение <tex>a\equiv b</tex> имеет место по нескольким модулям, то оно имеет место и по модулю равному [[Наименьшее общее кратное|НОК]] этих модулей. | ||
Строка 30: | Строка 32: | ||
*9. Если одна часть сравнения и модуль делятся на некоторое число, то и другая сторона сравнения должна делится на это число. | *9. Если одна часть сравнения и модуль делятся на некоторое число, то и другая сторона сравнения должна делится на это число. | ||
*10. Если <tex>a \equiv b(mod \text{ }m) </tex>, то <tex>(a,m) = (b,m) </tex>. | *10. Если <tex>a \equiv b(mod \text{ }m) </tex>, то <tex>(a,m) = (b,m) </tex>. | ||
− | |||
== Полная и приведенная система вычетов == | == Полная и приведенная система вычетов == |
Версия 02:46, 12 октября 2010
Содержание
Сравнения по модулю
Будем рассматривать целые числа в связи с остатками от деления их на данное целое число m, которое назовем модулем.
Каждому целому числу отвечает определенный остаток от деления его на m. Если двум целым a и b отвечает один и тот же остаток r, то они называются сравнимыми по модулю m.
Сравнимость для a и b записывается так :
Сравнимость чисел a и b по модулю m равносильна:
- а. Возможности представить a в форме , где t — целое.
- б. Делимости
- Действительно, из
- Обратно, из , представляя b в форме , выводим , где , значит .
на m.
- Действительно, из
Арифметика сравнений
Свойства сравнений
- 1. Два числа, сравнимые с третьим сравнимы между собой.
- Легко выводится из пункта "а".
- 2. Сравнения можно почленно складывать.
- Представляем сравнения, как в пункте "а" и складываем.
- 3. Сравнения можно почленно перемножать.
- Представляем сравнения, как в пункте "а", перемножаем, получим , где N—целое.
- 4. Обе части сравнения можно разделить на их общий делитель, если последний взаимно прост с модулем.
- Действительно, из , следует, что , поэтому .
- 5. Обе части сравнения можно умножить на одно и тоже число.
- Действительно, из , следует .
- 6. Обе части сравнения и модуль можно разделить на их общий делитель.
- 7. Если сравнение НОК этих модулей. имеет место по нескольким модулям, то оно имеет место и по модулю равному
- 8. Если сравнение имеет место по модулю m, то оно имеет место и по модулю d, равному любому делителю числа m.
- 9. Если одна часть сравнения и модуль делятся на некоторое число, то и другая сторона сравнения должна делится на это число.
- 10. Если , то .
Полная и приведенная система вычетов
Числа равноостаточные(сравнимые по модулю m) образуют класс чисел по модулю m.
Из такого определения следует, что всем числам класса отвечает один остаток r, и мы получим все числа класса,
если в форме
Любое число класса называется вычетом по модулю m. Вычет получаемый при , равный самому остатку r,
называется наименьшим неотрицательным вычетом.
Любые m чисел, попарно несравнимые по модулю m, образуют полную систему вычетов по этому модулю.
Согласно 10 свойству сравнений, числа одного класса по модулю m имеют одинаковый НОД. Особенно важны классы, содержащие числа, взаимно простые с модулем. Взяв вычет от каждого такого класса, получим приведенную систему вычетов по модулю m.
Решение линейных систем по модулю
Пусть
Поиск решений:
,
Составим новое сравнение ,
обозначим его ,
его решением будет , где - числитель подходящей дроби.
Пусть
После этого решения исходного сравнения запишутся так :