Сравнения, система вычетов, решение линейных систем по модулю — различия между версиями
(→Решение линейных систем по модулю) |
Bochkarev (обсуждение | вклад) (→Решение линейных систем по модулю) |
||
Строка 52: | Строка 52: | ||
== Решение линейных систем по модулю == | == Решение линейных систем по модулю == | ||
− | Пусть <tex> (a, | + | Пусть <tex> (a, m) = d </tex>. Сравнение <tex> ax \equiv b(mod \text{ }m)</tex> невозможно, если b не делится на '''d'''. При b, кратном '''d''', сравнение имеет '''d''' решений.<br> |
'''Поиск решений:'''<br> | '''Поиск решений:'''<br> | ||
<tex> ax \equiv b(mod \text{ }m)</tex>, <tex> (a, b) = d </tex> <br> | <tex> ax \equiv b(mod \text{ }m)</tex>, <tex> (a, b) = d </tex> <br> | ||
Строка 58: | Строка 58: | ||
обозначим его <tex> a_dx \equiv b_d(mod \text{ } m_d)</tex>. Пусть его решением будет <tex> x_0 </tex>, тогда остальные решения найдутся по следующей формуле: <tex> x_n = x_{n-1} - m_d </tex>, всего решений будет d. Если нахождение <tex> x_0 </tex> не является очевидным, то следует воспользоваться [[Цепная дробь|теорией цепных дробей]], и тогда <tex> x_0 = (-1)^{n-1}P_{n-1}b_d</tex>, где <tex> P_{n-1} </tex> - [[Цепная дробь | числитель подходящей дроби]]. | обозначим его <tex> a_dx \equiv b_d(mod \text{ } m_d)</tex>. Пусть его решением будет <tex> x_0 </tex>, тогда остальные решения найдутся по следующей формуле: <tex> x_n = x_{n-1} - m_d </tex>, всего решений будет d. Если нахождение <tex> x_0 </tex> не является очевидным, то следует воспользоваться [[Цепная дробь|теорией цепных дробей]], и тогда <tex> x_0 = (-1)^{n-1}P_{n-1}b_d</tex>, где <tex> P_{n-1} </tex> - [[Цепная дробь | числитель подходящей дроби]]. | ||
− | === Пример | + | === Примеры решения === |
+ | '''Пример 1.''' <br> | ||
+ | <tex> 12x \equiv 6(mod \text{ }18)</tex> <br> | ||
+ | Найдем НОД <tex>(12,18)=6 </tex> <br> | ||
+ | Перейдем к новому сравнению <tex> 2x \equiv 1(3) </tex> <br> | ||
+ | Легко находится <tex> x_0 = 2 </tex> <br> | ||
+ | Тогда ответом будет <tex> x_0 =2, x_1 = x_0 - \frac{m}{(a,m)}=-1, x_2 = -4</tex> |
Версия 04:49, 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.
Решение линейных систем по модулю
Пусть
Поиск решений:
,
Составим новое сравнение ,
обозначим его . Пусть его решением будет , тогда остальные решения найдутся по следующей формуле: , всего решений будет d. Если нахождение не является очевидным, то следует воспользоваться теорией цепных дробей, и тогда , где - числитель подходящей дроби.
Примеры решения
Пример 1.
Найдем НОД
Перейдем к новому сравнению
Легко находится
Тогда ответом будет