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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 5: Строка 5:
 
<math>a \equiv b(mod \text{ } m)</math> <br><br>
 
<math>a \equiv b(mod \text{ } m)</math> <br><br>
 
Сравнимость чисел '''a''' и '''b''' по модулю '''m''' равносильна:
 
Сравнимость чисел '''a''' и '''b''' по модулю '''m''' равносильна:
*1. Возможности представить '''a''' в форме <tex>\Huge{a = b + mt}</tex>, где t - целое.
+
*1. Возможности представить '''a''' в форме <tex>\Huge{a = b + mt}</tex>, где t {{---}} целое.
 
*2. Делимости <tex>\Huge{a - b}</tex> на '''m'''.
 
*2. Делимости <tex>\Huge{a - b}</tex> на '''m'''.
 
== Арифметика сравнений ==
 
== Арифметика сравнений ==
Строка 29: Строка 29:
 
называется '''наименьшим неотрицательным вычетом'''.<br><br>
 
называется '''наименьшим неотрицательным вычетом'''.<br><br>
 
Любые '''m''' чисел, попарно несравнимые по модулю '''m''', образуют '''полную систему вычетов''' по этому модулю.<br><br>
 
Любые '''m''' чисел, попарно несравнимые по модулю '''m''', образуют '''полную систему вычетов''' по этому модулю.<br><br>
Согласно 10-му свойству сравнений, числа одного класса по модулю '''m''' имеют одинаковый [[Наибольший общий делитель|НОД]]. Особенно важны классы, содержащие числа, взаимно простые с модулем. Взяв вычет от каждого такого класса, получим '''приведенную систему вычетов''' по модулю '''m'''.
+
Согласно 10 свойству сравнений, числа одного класса по модулю '''m''' имеют одинаковый [[Наибольший общий делитель|НОД]]. Особенно важны классы, содержащие числа, взаимно простые с модулем. Взяв вычет от каждого такого класса, получим '''приведенную систему вычетов''' по модулю '''m'''.
  
 
== Решение линейных систем по модулю ==
 
== Решение линейных систем по модулю ==

Версия 01:02, 12 октября 2010

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

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

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

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

  • 1. Возможности представить a в форме [math]\Huge{a = b + mt}[/math], где t — целое.
  • 2. Делимости [math]\Huge{a - b}[/math] на m.

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

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

  • 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]
  • 4. Обе части сравнения можно разделить на их общий делитель, если последний взаимно прост с модулем.
  • 5. Обе части сравнения можно умножить на одно и тоже число.
  • 6. Обе части сравнения и модуль можно разделить на их общий делитель.
  • 7. Если сравнение [math]a\equiv b[/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, b) = 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 \equiv (-1)^{n-1}P_{n-1}b_d(mod \text{ } m_d)[/math], где [math] P_{n-1} [/math] - числитель подходящей дроби. Пусть [math] P = (-1)^{n-1}P_{n-1}b_d [/math]
После этого решения исходного сравнения запишутся так : [math] x \equiv P; P+m_d; P+2m_d; \ldots ;P+dm_d (mod \text{ }m)[/math]