Свойства сравнений
сравнений
Ч.т.д.
|
|
|
| |
|
1) Слагаемое, |
стоящие в какой-либо части |
сравнения, можно |
|
переносить в другую часть, изменив его знак на противоположный. Действительно, пусть
а + b = с (mod m) —b = — b(modm)
тогда, сложив эти сравнения, имеем:
а + b — b = с — b(mod m)
а = с — b(mod т). (2.131)
2) К любой части сравнения можно прибавить любое число, кратное модулю.
В самом деле, пусть
а = b(mod т).
Используем очевидное сравнение
т • г = 0 (mod т). Складывая оба сравнения, имеем:
а + т • г = b(mod m) (2.132)
3) Обе части сравнения можно возвести в одну и ту же натуральную степень.
Это утверждение верно, так как, применив правило умножения к раз получим, что если
а = b(mod т),
то верно, что и
ап = bn(mod т), neN. (2.133)
4) Обе части сравнения можно умножить на одно и тоже целое
число.
Действительно, перемножая сравнение
|
а = b(mod пї) |
(2.134) |
|
|
с очевидным сравнением |
к = к (mod ти), |
(2.135) |
|
получим |
а - к = b • к (mod тп). |
(2.136) |
5) Обе части сравнения и модуль можно разделить на их общий
делитель.
|
Для доказательства, заметим, что если |
||
|
к • а = к • b(mod т ? к), |
(2.137) |
|
|
то |
к • а — к ? b • т- к. |
(2.138) |
|
Следовательно, |
а — b • т, |
(2.139) |
|
то есть |
а = b(mod т). |
|
6) Пусть т1-любой делитель числа т. Тогда, если а = b(mod пі), то а = b(mod mJ.
В самом деле, если
а = b(mod т),
то
а — b • т.
Но так как тг- делитель т, то
а — b • т1,
то есть
а = b(mod mJ.
7) Обе части сравнения можно разделить на их общий делитель, при условии, что этот общий делитель взаимно прост с модулем.
Для доказательства этого утверждения, рассмотрим верное сравнение а = b(mod т).
и пусть
|
а — аг ? d, b = Ьг • d, d • т. |
(2.140) |
|
|
Но из условия (d,m)=[ |
следует, что |
|
|
(с^ — Ьг) ? d • т |
(2.141) |
|
|
в том случае, когда |
а± — Ьг • т, |
(2.142) |
|
что означает, |
аг = bx (то dm). |
(2.143) |
8) Если одна часть сравнения и модуль делятся на какое - либо число, то и другая часть сравнения делиться на это число.
Действительно, пусть задано сравнение
а = b (mod т), что означает
а - b = mt. (2.144)
Левая часть равенства (2.144) делится на к, значит и правая часть так же делится на к:
(b + mt) : к. (2.145)
Но т’.к по условию, следовательно, и b также кратно к.
9) Если сравнение а и b верно для нескольких разных модулей, то оно верно и но модулю, равному наименьшему общему кратному этих модулей.
Это так, потому что, если
а = b(modm1)a = b (modm2>) (2.146)
то а - b так же делится и на т1 и на т2. Но тогда а - b делится и на наименьшее общее кратное тг и т2.
10) Если а = b(mod т), то (а,т) = (Ь,т).
Для доказательства этого свойства предположим, что наибольший общий делитель чисел а и т, равен d:
(а,т) = d.
Что означает, а • d и m • d, то есть
а = dk,m = dn. (2.147)
Так как,
а = b (mod m), то
а = b + mt, dk = b + dnt. (2.148)
Но левая часть равенства (2.149) кратна d, значит и правая должна быть кратна d:
dn • п, (2.149)
что означает, что и b : d, то есть - верность равенства:
(а,т) = (Ь,т). (2.150)
И так, коротко запишем перечисленные свойства сравнений'.
г а + pm = b(modm)
а = b (modm)=> <
<ар
а = b + pm(mod т) ак = bk(modm) + b = b + p(mod т) ар = bp (mod m) = bp(mod mp),p Ф 0.
(2.151)
_ , f a — at a y(a+c = b±d (mod m)
= b(modm),c = d(modm)=>] , ,, , . (2.152)
- ( ac = bd (mod m).
- 13.4 Вычеты
Числа, сравнимые по модулю т образуют класс чисел по модулю т.
Таким образом, всем числам одного класса сопоставлен один и тот же остаток т.
Получается, в определенном классе находится все числа вида
т ? q + т, q є IL.
Например, рассмотрим все целые числа на числовой оси, и разобьем это множество чисел на классы по mod 3 следующим образом:
к первому классу, обозначим его как б, отнесем все числа, которые при делении на 3 дают в остатке 0, то есть это числа ... —6, —3, 0, 3,6,... (на оси обозначим о);
к классу Ї отнесем соответственно ...,—5, —2, 1, 4, 7, ... (на оси обозначим •);
к классу 2 отнесем числа ..., —4, —1,2, 5, ... (на оси обозначим *).
Итак, мы все множество целых чисел разбили на три класса - класс нуля б, класс единицы I и класс двойки 2:
Очевидно, что, например 2 = —4, так как числа 2 и —4 они стоят друг от друга на чисто кратное трем: 2 — (—4) = 6:3. Также, например,—5 = Ї или —6 = —3 и так далее.
Полученные классы чисел называются классами вычетов по mod 3. Обобщим сказанное:
Классом вычетов по mod т называется совокупность целых чисел, имеющих при делении на т одинаковые остатки.
Любое число из класса вычетов по заданному т будем называть вычетом по mod т этого класса.
Очевидно, что всякий вычет из класса вычетов по модулю т определяет этот класс.
Класс вычетов, содержащий число а, будем обозначать через-^? При этом, конечно, нужно всегда оговаривать модуль.
Так как при делении целого числа на натуральное т возможны т различных остатков 0,1,... ,т — 1, то, соответственно, мы можем говорить о т различных классах вычетов по модулю т.
б - класс вычетов, соответствующих нулю, то есть в этом классе «сидят» все числа, которые делятся на т нацело (остаток равен нулю).
Далее, Ї - класс чисел дающих при делении на т остаток равный 1, то есть
Ї = (к -тп + 1,кє%} (2.153)
и так далее,
т — 1 = [к ? т + (т — 1), кє (2.154)
Получаем, что класс вычетов а это:
а = {к • т + а, кє Z} (2.155)
Множество классов всех вычетов по модулю т, обозначают как 7Lm.
Очевидно, что при некотором т є N, т > 2 можно построить множество = {б, Ї,..., т — 1), причем, если а = Ь, то это означает, что
а — b = к ? т (2.156)
Также очевидно, что никакие 2 класса вычетов не пересекаются, так как одно число не может давать двух различных остатков при делении на т.
Так же, очевидно, что объединение всех классов вычетов по модулю тдает все множество Z, поскольку любое целое число лежит в одном из классов.
Совокупность вычетов, взятых по одному из каждого класса вычетов по модулю т назовем полной системой вычетов.
Например, числа 0, 1, 2, 3 - составляют полную систему вычетов по модулю 4; и —4, —3, 6, 7 - также полная система вычетов по модулю 4. Но числа —4, —3, 0, 1, 2; 6 - уже не полная система вычетов по модулю 4, потому что нет числа, которое бы при делении на четверку давало бы остаток, равный трем.
Назовем совокупность всех вычетов из полной системы, взаимно простых с модулем т, приведенной системой вычетов по модулю т.
Например, совокупность чисел 0, 1, 2, 3 - образуют приведенную систему вычетов по модулю 4; тогда как совокупность —4. —3, 6, 7 - не является приведенной система вычетов по модулю 4, поскольку вычеты -4 и 6 не являются взаимно простыми с модулем 4.
