Сравнения — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Полная и приведенная система вычетов)
м (rollbackEdits.php mass rollback)
 
(не показано 5 промежуточных версий 3 участников)
Строка 13: Строка 13:
 
*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>
*4. Обе части сравнения можно разделить на их общий делитель, если последний взаимно прост с модулем.
+
*4. Обе части сравнения можно разделить на их общий делитель, если последний не взаимно прост с модулем.
*5. Обе части сравнения можно умножить на одно и тоже число.
+
*5. Обе части сравнения можно умножить на одно и тоже число, кроме общего делителя.
*6. Обе части сравнения и модуль можно разделить на их общий делитель.
+
*6. Обе части сравнения и модуль можно умножить на их общий делитель.
 
*7. Если сравнение <tex>a\equiv b</tex> имеет место по нескольким модулям, то оно имеет место и по модулю равному [[Наименьшее общее кратное|НОК]] этих модулей.
 
*7. Если сравнение <tex>a\equiv b</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>.
  
Строка 25: Строка 25:
 
Числа равноостаточные(сравнимые по модулю '''m''') образуют класс чисел по модулю '''m'''.
 
Числа равноостаточные(сравнимые по модулю '''m''') образуют класс чисел по модулю '''m'''.
 
Из такого определения следует, что всем числам класса отвечает один остаток '''r''', и мы получим все числа класса,
 
Из такого определения следует, что всем числам класса отвечает один остаток '''r''', и мы получим все числа класса,
если в форме <tex>mt + r </tex> заставим t пробегать все целые числа. Таким образом для каждого значения остатка имеется свой класс чисел.
+
если в форме <tex>mt + r </tex> заставим t пробегать все целые числа. Таким образом для каждого значения остатка имеется свой класс чисел. <br><br>
 +
Любое число класса называется '''вычетом''' по модулю '''m'''. Вычет получаемый при <tex> t = 0</tex>, равный самому остатку '''r''',
 +
называется '''наименьшим неотрицательным вычетом'''.<br><br>
 +
Любые '''m''' чисел, попарно несравнимые по модулю '''m''', образуют '''полную систему вычетов''' по этому модулю.<br><br>
 +
Согласно 10-му свойству сравнений, числа одного класса по модулю '''m''' имеют одинаковый [[Наибольший общий делитель|НОД]]. Особенно важны классы, содержащие числа, взаимно простые с модулем. Взяв вычет от каждого такого класса, получим '''приведенную систему вычетов''' по модулю '''m'''.

Текущая версия на 19:38, 4 сентября 2022

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

Будем рассматривать целые числа в связи с остатками от деления их на данное целое число 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.