175
правок
Изменения
Новая страница: «== Сравнения по модулю == Будем рассматривать целые числа в связи с остатками от деления их …»
== Сравнения по модулю ==
Будем рассматривать целые числа в связи с остатками от деления их на данное целое число '''m''', которое назовем модулем.
Каждому целому числу отвечает определенный остаток от деления его на '''m'''. Если двум целым '''a''' и '''b''' отвечает один и тот же остаток '''r''', то они называются сравнимыми по модулю '''m'''.<br><br>
Сравнимость для '''a''' и '''b''' записывается так : <br>
<math>a \equiv b(mod \text{ } m)</math> <br><br>
Сравнимость чисел '''a''' и '''b''' по модулю '''m''' равносильна:
*1. Возможности представить '''a''' в форме <tex>\Huge{a = b + mt}</tex>, где t - целое.
*2. Делимости <tex>\Huge{a - b}</tex> на '''m'''.
== Арифметика сравнений ==
=== Свойства сравнений ===
*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>
*3. Сравнения можно почленно перемножать. <tex> a_1a_2a_3 \equiv b_1b_2b_3(mod \text{ }m)</tex>
*4. Обе части сравнения можно разделить на их общий делитель, если последний взаимно прост с модулем.
*5. Обе части сравнения можно умножить на одно и тоже число.
*6. Обе части сравнения и модуль можно разделить на их общий делитель.
*7. Если сравнение <tex>a\equiv b</tex> имеет место по нескольким модулям, то оно имеет место и по модулю равному [[Наименьшее общее кратное|НОК]] этих модулей.
*8. Если сравнение имеет место по модулю '''m''', то оно имеет место и по модулю '''d''', равному любому делителю числа '''m'''.
*9. Если одна часть сравнения и модуль делятся на некоторое число, то и другая сторона сравнения должна делится на это число.
*10. Если <tex>a \equiv b(mod \text{ }m) </tex>, то <tex>(a,m) = (b,m) </tex>.
== Полная и приведенная система вычетов ==
Числа равноостаточные(сравнимые по модулю '''m''') образуют класс чисел по модулю '''m'''.
Из такого определения следует, что всем числам класса отвечает один остаток '''r''', и мы получим все числа класса,
если в форме <tex>mt + r </tex> заставим t пробегать все целые числа. Таким образом для каждого значения остатка имеется свой класс чисел. <br><br>
Любое число класса называется '''вычетом''' по модулю '''m'''. Вычет получаемый при <tex> t = 0</tex>, равный самому остатку '''r''',
называется '''наименьшим неотрицательным вычетом'''.<br><br>
Любые '''m''' чисел, попарно несравнимые по модулю '''m''', образуют '''полную систему вычетов''' по этому модулю.<br><br>
Согласно 10-му свойству сравнений, числа одного класса по модулю '''m''' имеют одинаковый [[Наибольший общий делитель|НОД]]. Особенно важны классы, содержащие числа, взаимно простые с модулем. Взяв вычет от каждого такого класса, получим '''приведенную систему вычетов''' по модулю '''m'''.
Будем рассматривать целые числа в связи с остатками от деления их на данное целое число '''m''', которое назовем модулем.
Каждому целому числу отвечает определенный остаток от деления его на '''m'''. Если двум целым '''a''' и '''b''' отвечает один и тот же остаток '''r''', то они называются сравнимыми по модулю '''m'''.<br><br>
Сравнимость для '''a''' и '''b''' записывается так : <br>
<math>a \equiv b(mod \text{ } m)</math> <br><br>
Сравнимость чисел '''a''' и '''b''' по модулю '''m''' равносильна:
*1. Возможности представить '''a''' в форме <tex>\Huge{a = b + mt}</tex>, где t - целое.
*2. Делимости <tex>\Huge{a - b}</tex> на '''m'''.
== Арифметика сравнений ==
=== Свойства сравнений ===
*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>
*3. Сравнения можно почленно перемножать. <tex> a_1a_2a_3 \equiv b_1b_2b_3(mod \text{ }m)</tex>
*4. Обе части сравнения можно разделить на их общий делитель, если последний взаимно прост с модулем.
*5. Обе части сравнения можно умножить на одно и тоже число.
*6. Обе части сравнения и модуль можно разделить на их общий делитель.
*7. Если сравнение <tex>a\equiv b</tex> имеет место по нескольким модулям, то оно имеет место и по модулю равному [[Наименьшее общее кратное|НОК]] этих модулей.
*8. Если сравнение имеет место по модулю '''m''', то оно имеет место и по модулю '''d''', равному любому делителю числа '''m'''.
*9. Если одна часть сравнения и модуль делятся на некоторое число, то и другая сторона сравнения должна делится на это число.
*10. Если <tex>a \equiv b(mod \text{ }m) </tex>, то <tex>(a,m) = (b,m) </tex>.
== Полная и приведенная система вычетов ==
Числа равноостаточные(сравнимые по модулю '''m''') образуют класс чисел по модулю '''m'''.
Из такого определения следует, что всем числам класса отвечает один остаток '''r''', и мы получим все числа класса,
если в форме <tex>mt + r </tex> заставим t пробегать все целые числа. Таким образом для каждого значения остатка имеется свой класс чисел. <br><br>
Любое число класса называется '''вычетом''' по модулю '''m'''. Вычет получаемый при <tex> t = 0</tex>, равный самому остатку '''r''',
называется '''наименьшим неотрицательным вычетом'''.<br><br>
Любые '''m''' чисел, попарно несравнимые по модулю '''m''', образуют '''полную систему вычетов''' по этому модулю.<br><br>
Согласно 10-му свойству сравнений, числа одного класса по модулю '''m''' имеют одинаковый [[Наибольший общий делитель|НОД]]. Особенно важны классы, содержащие числа, взаимно простые с модулем. Взяв вычет от каждого такого класса, получим '''приведенную систему вычетов''' по модулю '''m'''.
