Сравнения, система вычетов, решение линейных систем по модулю
Будем рассматривать целые числа в связи с остатками от деления их на данное целое число m, которое назовем модулем. Каждому целому числу отвечает определенный остаток от деления его на m. Если двум целым a и b отвечает один и тот же остаток r, то они называются сравнимыми по модулю m.
Сравнимость для a и b записывается так :
[math]a \equiv b(mod \text < >m)[/math]
Сравнимость чисел a и b по модулю m равносильна:
- а. Возможности представить a в форме [math]\Huge[/math] , где t — целое.
- б. Делимости [math]\Huge[/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[/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.
Решение линейных систем по модулю
Примеры решения
Пример 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=-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_ = 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] .как сравнить модули числа?
Если числа целые, то большем будет то, в котором число цифр больше. Если число цифр одинаково, большим будет то, первая цифра которого расположена в ряду 0 1 2 3 4 5 6 7 8 9 правее. Если первые цифры одинаковы, то сравниваются вторые цифры, если и они одинаковы, то берутся третьи, потом четвёртые, и т. д. В случае равенства всех соответствующих цифр числа равны.
Рекомендации Учи.Ответов
Разобраться с этим и другими вопросами поможет курс Учи.ру по математике для 6 класса
Пользователь 4 года назад
Модуль числа а равен самому числу а, если а является положительным, числу -а, если а является отрицательным, или 0, если а=0 Т.е. модуль это положительная часть числа и сравнивают модуль как все обычные цифры, например сравним |17| и |-19| |17| = 17, а |-19| = 19, следовательно осталось сравнить получившиеся ответы (17 и 19) 17 Спасибо 0
1. Сравнение рациональных чисел
Первая ситуация. Вчера термометр показывал \(-27\) \(°С\) , сегодня температура повысилась до \(-20\) \(°С\) .
Температура вчера была меньше, чем сегодня. Число \(-27\) меньше числа \(-20\), или \( -27 < -20\).
Заметим, что если сравнивать модули чисел, то знак будет наоборот \(>\).
− 27 > − 20 ; 27 > 20 .
Чтобы сравнить два отрицательных числа, нужно сравнить их модули: отрицательное число с большим модулем будет меньше.
− 24,7 < − 20,9 ; − 1 4 < − 1 8 ; − 2 3 7 >− 5 1 7 .
Сравнение по модулю натурального числа
Говорят, что два целых числа a и b сравнимы по модулю натурального числа n, если при делении на n они дают одинаковые остатки. Другими словами, a и b сравнимы по модулю n, если их разность a – b делится на n.
Пример: 32 и 39 сравнимы по модулю 7, так как 32 = 7∙4 + 4, 39 = 7∙5 + 4.
Утверждение a и b сравнимы по модулю n записывается в виде:
Отношение сравнения обладает многими свойствами обычных равенств. Например, если
a 1 a 2 ≡ b 1 b 2 ( mod n ) a_\equiv b_b_<\pmod
>> и a 1 + a 2 ≡ b 1 + b 2 ( mod n ) . +a_\equiv b_+b_<\pmod >.> Классы вычетов [ ]
Сравнение по модулю n является отношением эквивалентности на множестве целых чисел Z > , и классы вычетов по модулю n представляют собой классы эквивалентности. Множество всех классов вычетов по модулю n обозначается Z n _> или Z / n Z /n\mathbb > .
[ a ] n + [ b ] n = [ a + b ] n +[b]_=[a+b]_> [ a ] n ⋅ [ b ] n = [ a ⋅ b ] n \cdot [b]_=[a\cdot b]_>
Ссылки [ ]
- Виленкин Н. Я., Сравнения и классы вычетов, Квант, № 10, 1978.
- Виноградов И. М., Основы теории чисел, М.: ГИТТЛ, 1952.
- Сизый С. В., Лекции по теории чисел.