Сравнения, система вычетов, решение линейных систем по модулю — различия между версиями
Bochkarev (обсуждение | вклад) (→Китайская теорема об остатках) |
м (rollbackEdits.php mass rollback) |
||
(не показано 28 промежуточных версий 4 участников) | |||
Строка 1: | Строка 1: | ||
− | |||
== Сравнения по модулю == | == Сравнения по модулю == | ||
Будем рассматривать целые числа в связи с остатками от деления их на данное целое число '''m''', которое назовем модулем. | Будем рассматривать целые числа в связи с остатками от деления их на данное целое число '''m''', которое назовем модулем. | ||
Каждому целому числу отвечает определенный остаток от деления его на '''m'''. Если двум целым '''a''' и '''b''' отвечает один и тот же остаток '''r''', то они называются сравнимыми по модулю '''m'''.<br><br> | Каждому целому числу отвечает определенный остаток от деления его на '''m'''. Если двум целым '''a''' и '''b''' отвечает один и тот же остаток '''r''', то они называются сравнимыми по модулю '''m'''.<br><br> | ||
Сравнимость для '''a''' и '''b''' записывается так : <br> | Сравнимость для '''a''' и '''b''' записывается так : <br> | ||
− | < | + | <tex>a \equiv b(mod \text{ } m)</tex> <br><br> |
Сравнимость чисел '''a''' и '''b''' по модулю '''m''' равносильна: | Сравнимость чисел '''a''' и '''b''' по модулю '''m''' равносильна: | ||
− | * | + | *а. Возможности представить '''a''' в форме <tex>\Huge{a = b + mt}</tex>, где t {{---}} целое. |
− | * | + | *б. Делимости <tex>\Huge{a - b}</tex> на '''m'''. |
+ | ** Действительно, из <tex> a \equiv b(mod \text{ } m) </tex> следует <tex> a = mq + r, \text{ } b = mq_1 + r </tex>, откуда <tex> a - b = m(q-q_1)</tex>, и <tex> a = b + mt</tex>, где <tex> t = q - q_1</tex>.<br> | ||
+ | ** Обратно, из <tex>\Huge{a = b + mt}</tex>, представляя '''b''' в форме <tex> b = mq_1 + r </tex>, выводим <tex> a = mq + r </tex>, где <tex> q = q_1 + t </tex>, значит <tex> a \equiv b(mod \text{ } m) </tex>. | ||
== Арифметика сравнений == | == Арифметика сравнений == | ||
=== Свойства сравнений === | === Свойства сравнений === | ||
*1. Два числа, сравнимые с третьим сравнимы между собой. <tex>a \equiv c(mod \text{ }m) \text{, } b \equiv c(mod \text{ }m) \Rightarrow a \equiv b(mod \text{ }m)</tex> | *1. Два числа, сравнимые с третьим сравнимы между собой. <tex>a \equiv c(mod \text{ }m) \text{, } b \equiv c(mod \text{ }m) \Rightarrow a \equiv b(mod \text{ }m)</tex> | ||
+ | ** Легко выводится из пункта "а". | ||
+ | |||
*2. Сравнения можно почленно складывать. <tex> a_1 + a_2 + a_3 \equiv b_1 + b_2 + b_3(mod \text{ }m)</tex> | *2. Сравнения можно почленно складывать. <tex> a_1 + a_2 + a_3 \equiv b_1 + b_2 + b_3(mod \text{ }m)</tex> | ||
+ | ** Представляем сравнения, как в пункте "а" и складываем. | ||
+ | |||
*3. Сравнения можно почленно перемножать. <tex> a_1a_2a_3 \equiv b_1b_2b_3(mod \text{ }m)</tex> | *3. Сравнения можно почленно перемножать. <tex> a_1a_2a_3 \equiv b_1b_2b_3(mod \text{ }m)</tex> | ||
+ | ** Представляем сравнения, как в пункте "а", перемножаем, получим <tex> a_1a_2a_3 = b_1b_2b_3+mN</tex>, где N{{---}}целое. | ||
+ | |||
*4. Обе части сравнения можно разделить на их общий делитель, если последний взаимно прост с модулем. | *4. Обе части сравнения можно разделить на их общий делитель, если последний взаимно прост с модулем. | ||
+ | ** Действительно, из <tex>a \equiv b(mod \text{ } m)</tex>, <tex> a = a_1d, b = b_1d, (d,m)=1</tex> следует, что <tex> a-b = (a_1 - b_1)d \vdots m </tex>, поэтому <tex> a_1 \equiv b_1(mod \text{ } m)</tex>. | ||
+ | |||
*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. Обе части сравнения и модуль можно разделить на их общий делитель. | ||
+ | ** Действительно, пусть <tex>a \equiv b(mod \text{ } m), a = a_1d, b=b_1d, m=m_1d</tex>, отсюда <tex> a= b+mt, a_1d =b_1d +m_1dt, a_1 =b_1 +m_1t</tex>, и, следовательно, <tex>a_1 \equiv b_1(mod \text{ } m_1)</tex>. | ||
+ | |||
*7. Если сравнение <tex>a\equiv b</tex> имеет место по нескольким модулям, то оно имеет место и по модулю равному [[Наименьшее общее кратное|НОК]] этих модулей. | *7. Если сравнение <tex>a\equiv b</tex> имеет место по нескольким модулям, то оно имеет место и по модулю равному [[Наименьшее общее кратное|НОК]] этих модулей. | ||
+ | **В самом деле, из <tex> a \equiv b(mod \text{ }m_1),\ldots,a \equiv b(mod \text{ }m_k)</tex> следует, что разность <tex> a-b </tex> делится на все модули <tex> m_1,m_2,\ldots,m_k</tex>. Поэтому она должна делиться и на их [[Наименьшее общее кратное|НОК]]. | ||
+ | |||
*8. Если сравнение имеет место по модулю '''m''', то оно имеет место и по модулю '''d''', равному любому делителю числа '''m'''. | *8. Если сравнение имеет место по модулю '''m''', то оно имеет место и по модулю '''d''', равному любому делителю числа '''m'''. | ||
− | *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>. | ||
− | + | ** Следует из пункта "а" по свойству [[Наибольший общий делитель|НОДа]]. | |
== Полная и приведенная система вычетов == | == Полная и приведенная система вычетов == | ||
Строка 30: | Строка 49: | ||
называется '''наименьшим неотрицательным вычетом'''.<br><br> | называется '''наименьшим неотрицательным вычетом'''.<br><br> | ||
Любые '''m''' чисел, попарно несравнимые по модулю '''m''', образуют '''полную систему вычетов''' по этому модулю.<br><br> | Любые '''m''' чисел, попарно несравнимые по модулю '''m''', образуют '''полную систему вычетов''' по этому модулю.<br><br> | ||
− | Согласно 10 | + | Согласно 10 свойству сравнений, числа одного класса по модулю '''m''' имеют одинаковый [[Наибольший общий делитель|НОД]]. Особенно важны классы, содержащие числа, взаимно простые с модулем. Взяв вычет от каждого такого класса, получим '''приведенную систему вычетов''' по модулю '''m'''. |
== Решение линейных систем по модулю == | == Решение линейных систем по модулю == | ||
− | = | + | Пусть <tex> (a, m) = d </tex>. Сравнение <tex> ax \equiv b(mod \text{ }m)</tex> невозможно, если b не делится на '''d'''. При b, кратном '''d''', сравнение имеет '''d''' решений.<br> |
− | + | '''Поиск решений:'''<br> | |
− | + | <tex> ax \equiv b(mod \text{ }m)</tex>, <tex> (a, b) = d </tex> <br> | |
+ | Составим новое сравнение <tex> \frac{a}{d}x \equiv \frac{b}{d}(mod \text{ } \frac{m}{d})</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>(следует понимать, что <tex> x_i </tex> вычет по модулю, поэтому в этой формуле можно сменить знак, для удобства), всего решений будет d. Если нахождение <tex> x_0 </tex> не является очевидным, то следует воспользоваться [[Цепная дробь|теорией цепных дробей]], и тогда <tex> x_0 = (-1)^{n-1}P_{n-1}b_d</tex>, где <tex> P_{n-1} </tex> - [[Цепная дробь | числитель подходящей дроби]]. | ||
− | == | + | === Примеры решения === |
− | <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> | |
− | |||
− | + | '''Пример 2.''' <br> | |
− | ''' | + | <tex> 111x \equiv 75(mod \text{ }321)</tex> <br> |
− | + | Найдем НОД <tex>(111,321)=3 </tex>, 75 кратно 3, значит имеем 3 решения <br> | |
− | + | Перейдем к новому сравнению <tex> 37x \equiv 25(107) </tex> <br> | |
− | + | Воспользуемся цепными дробями, в нашем случае <tex> n=4, p_{n-1} = 26</tex>, значит <tex> x_0 \equiv -26\cdot 25 (107) \equiv 99(107) </tex> <br> | |
+ | Тогда ответом будет <tex> x_0 = 99, x_1 = 206, x_2 = 313 </tex>. |
Текущая версия на 19:20, 4 сентября 2022
Содержание
Сравнения по модулю
Будем рассматривать целые числа в связи с остатками от деления их на данное целое число 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.
Найдем НОД
Перейдем к новому сравнению
Легко находится
Тогда ответом будет
Пример 2.
Найдем НОД , 75 кратно 3, значит имеем 3 решения
Перейдем к новому сравнению
Воспользуемся цепными дробями, в нашем случае , значит
Тогда ответом будет .