Сравнения, система вычетов, решение линейных систем по модулю — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Свойства сравнений)
(не показано 12 промежуточных версий 2 участников)
Строка 5: Строка 5:
 
<tex>a \equiv b(mod \text{ } m)</tex> <br><br>
 
<tex>a \equiv b(mod \text{ } m)</tex> <br><br>
 
Сравнимость чисел '''a''' и '''b''' по модулю '''m''' равносильна:
 
Сравнимость чисел '''a''' и '''b''' по модулю '''m''' равносильна:
*1. Возможности представить '''a''' в форме <tex>\Huge{a = b + mt}</tex>, где t {{---}} целое.
+
*а. Возможности представить '''a''' в форме <tex>\Huge{a = b + mt}</tex>, где t {{---}} целое.
*2. Делимости <tex>\Huge{a - b}</tex> на '''m'''.
+
*б. Делимости <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>.
 
+
** Следует из пункта "а" по свойству [[Наибольший общий делитель|НОДа]].
  
 
== Полная и приведенная система вычетов ==
 
== Полная и приведенная система вычетов ==
Строка 32: Строка 52:
  
 
== Решение линейных систем по модулю ==
 
== Решение линейных систем по модулю ==
Пусть <tex> (a, b) = d </tex>. Сравнение <tex> ax \equiv b(mod \text{ }m)</tex> невозможно, если b не делится на d. При b, кратном d, сравнение имеет d решений.<br>
+
Пусть <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>
 
Составим новое сравнение <tex> \frac{a}{d}x \equiv \frac{b}{d}(mod \text{ } \frac{m}{d})</tex>,
 
Составим новое сравнение <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> 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> x \equiv (-1)^{n-1}P_{n-1}b_d(mod \text{ } m_d)</tex>, где <tex> P_{n-1} </tex> - [[Цепная дробь | числитель подходящей дроби]].
+
 
Пусть <tex> P = (-1)^{n-1}P_{n-1}b_d </tex> <br>
+
=== Примеры решения ===
После этого решения исходного сравнения запишутся так : <tex> x \equiv P; P+m_d; P+2m_d; \ldots ;P+dm_d (mod \text{ }m)</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>.

Версия 17:16, 25 марта 2012

Сравнения по модулю

Будем рассматривать целые числа в связи с остатками от деления их на данное целое число m, которое назовем модулем. Каждому целому числу отвечает определенный остаток от деления его на m. Если двум целым a и b отвечает один и тот же остаток r, то они называются сравнимыми по модулю m.

Сравнимость для a и b записывается так :
[math]a \equiv b(mod \text{ } m)[/math]

Сравнимость чисел a и b по модулю m равносильна:

  • а. Возможности представить a в форме [math]\Huge{a = b + mt}[/math], где t — целое.
  • б. Делимости [math]\Huge{a - b}[/math] на m.
    • Действительно, из [math] a \equiv b(mod \text{ } m) [/math] следует [math] a = mq + r, \text{ } b = mq_1 + r [/math], откуда [math] a - b = m(q-q_1)[/math], и [math] a = b + mt[/math], где [math] t = q - q_1[/math].
    • Обратно, из [math]\Huge{a = b + mt}[/math], представляя b в форме [math] b = mq_1 + r [/math], выводим [math] a = mq + r [/math], где [math] q = q_1 + t [/math], значит [math] a \equiv b(mod \text{ } m) [/math].

Арифметика сравнений

Свойства сравнений

  • 1. Два числа, сравнимые с третьим сравнимы между собой. [math]a \equiv c(mod \text{ }m) \text{, } b \equiv c(mod \text{ }m) \Rightarrow a \equiv b(mod \text{ }m)[/math]
    • Легко выводится из пункта "а".
  • 2. Сравнения можно почленно складывать. [math] a_1 + a_2 + a_3 \equiv b_1 + b_2 + b_3(mod \text{ }m)[/math]
    • Представляем сравнения, как в пункте "а" и складываем.
  • 3. Сравнения можно почленно перемножать. [math] a_1a_2a_3 \equiv b_1b_2b_3(mod \text{ }m)[/math]
    • Представляем сравнения, как в пункте "а", перемножаем, получим [math] a_1a_2a_3 = b_1b_2b_3+mN[/math], где N—целое.
  • 4. Обе части сравнения можно разделить на их общий делитель, если последний взаимно прост с модулем.
    • Действительно, из [math]a \equiv b(mod \text{ } m)[/math], [math] a = a_1d, b = b_1d, (d,m)=1[/math] следует, что [math] a-b = (a_1 - b_1)d \vdots m [/math], поэтому [math] a_1 \equiv b_1(mod \text{ } m)[/math].
  • 5. Обе части сравнения можно умножить на одно и тоже число.
    • Действительно, из [math]a \equiv b(mod \text{ } m)[/math], следует [math] a = b+mt, ak =bk +mkt [/math], и, следовательно, [math]ak \equiv bk(mod \text{ } mk)[/math].
  • 6. Обе части сравнения и модуль можно разделить на их общий делитель.
    • Действительно, пусть [math]a \equiv b(mod \text{ } m), a = a_1d, b=b_1d, m=m_1d[/math], отсюда [math] a= b+mt, a_1d =b_1d +m_1dt, a_1 =b_1 +m_1t[/math], и, следовательно, [math]a_1 \equiv b_1(mod \text{ } m_1)[/math].
  • 7. Если сравнение [math]a\equiv b[/math] имеет место по нескольким модулям, то оно имеет место и по модулю равному НОК этих модулей.
    • В самом деле, из [math] a \equiv b(mod \text{ }m_1),\ldots,a \equiv b(mod \text{ }m_k)[/math] следует, что разность [math] a-b [/math] делится на все модули [math] m_1,m_2,\ldots,m_k[/math]. Поэтому она должна делиться и на их НОК.
  • 8. Если сравнение имеет место по модулю m, то оно имеет место и по модулю d, равному любому делителю числа m.
    • Следует из пункта "б".
  • 9. Если одна часть сравнения и модуль делятся на некоторое число, то и другая сторона сравнения должна делиться на это число.
    • Следует из пункта "а".
  • 10. Если [math]a \equiv b(mod \text{ }m) [/math], то [math](a,m) = (b,m) [/math].
    • Следует из пункта "а" по свойству НОДа.

Полная и приведенная система вычетов

Числа равноостаточные(сравнимые по модулю m) образуют класс чисел по модулю m. Из такого определения следует, что всем числам класса отвечает один остаток r, и мы получим все числа класса, если в форме [math]mt + r [/math] заставим t пробегать все целые числа. Таким образом для каждого значения остатка имеется свой класс чисел.

Любое число класса называется вычетом по модулю m. Вычет получаемый при [math] t = 0[/math], равный самому остатку r, называется наименьшим неотрицательным вычетом.

Любые m чисел, попарно несравнимые по модулю m, образуют полную систему вычетов по этому модулю.

Согласно 10 свойству сравнений, числа одного класса по модулю m имеют одинаковый НОД. Особенно важны классы, содержащие числа, взаимно простые с модулем. Взяв вычет от каждого такого класса, получим приведенную систему вычетов по модулю m.

Решение линейных систем по модулю

Пусть [math] (a, m) = d [/math]. Сравнение [math] ax \equiv b(mod \text{ }m)[/math] невозможно, если b не делится на d. При b, кратном d, сравнение имеет d решений.
Поиск решений:
[math] ax \equiv b(mod \text{ }m)[/math], [math] (a, b) = d [/math]
Составим новое сравнение [math] \frac{a}{d}x \equiv \frac{b}{d}(mod \text{ } \frac{m}{d})[/math], обозначим его [math] a_dx \equiv b_d(mod \text{ } m_d)[/math]. Пусть его решением будет [math] x_0 [/math], тогда остальные решения найдутся по следующей формуле: [math] x_n = x_{n-1} - m_d [/math](следует понимать, что [math] x_i [/math] вычет по модулю, поэтому в этой формуле можно сменить знак, для удобства), всего решений будет d. Если нахождение [math] x_0 [/math] не является очевидным, то следует воспользоваться теорией цепных дробей, и тогда [math] x_0 = (-1)^{n-1}P_{n-1}b_d[/math], где [math] P_{n-1} [/math] - числитель подходящей дроби.

Примеры решения

Пример 1.
[math] 12x \equiv 6(mod \text{ }18)[/math]
Найдем НОД [math](12,18)=6 [/math]
Перейдем к новому сравнению [math] 2x \equiv 1(3) [/math]
Легко находится [math] x_0 = 2 [/math]
Тогда ответом будет [math] x_0 =2, x_1 = x_0 - \frac{m}{(a,m)}=-1, x_2 = -4[/math]

Пример 2.
[math] 111x \equiv 75(mod \text{ }321)[/math]
Найдем НОД [math](111,321)=3 [/math], 75 кратно 3, значит имеем 3 решения
Перейдем к новому сравнению [math] 37x \equiv 25(107) [/math]
Воспользуемся цепными дробями, в нашем случае [math] n=4, p_{n-1} = 26[/math], значит [math] x_0 \equiv -26\cdot 25 (107) \equiv 99(107) [/math]
Тогда ответом будет [math] x_0 = 99, x_1 = 206, x_2 = 313 [/math].