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

Сравнение по модулю. Основные понятия и определения

Пусть заданы a, beZ, и meN.

Числа а и b сравнимы по mod т, если они имеют одинаковый остаток при делении на т.

Запись:

a = b(modm). (2.109)

Например,

• 1) Так как 26 = 5 • 5 + 1 и 16 = 5 • 3 + 1, то
• 26 = 16(тос/ 5).
• 2) Так как 24 = 4 ? 6 и 16 = 4 ? 4, то
• 24 = 16(mod 4).

Очевидно, ноль кратен любому натуральному числу, то есть 0 • т, а значит верно,что

• 24 = 0(mod 4).
• 16 = 0(mod 4).

Теорема 2.40

Целое число а сравнимо с целым b по mod т, тогда и только тогда, когда их разность делится на т, то есть

а = b(mod т) <=> а — b • т. (2.110)

Доказательство. Пусть верно что а = b(mod т).

Докажем, что а — b • т.

а = b(mod т) означает, что при делении чисел а и b на натуральное т, получается одинаковый остаток, то есть, что

а = к ? т + г

b = п • т + г (2.111)

Отсюда следует, что

а — b = (к — п) -т'-.т (2.112)

то есть верно а — b : т

Теперь, допустим, что верно

а — b • т (2.113)

и докажем, что при делении а и b на т получится равный остаток, то есть, что

а = b(mod т). Имеем,

а — b • т.

Пусть число а имеет остаток г_1? а целое b имеет остаток г₂:

а = к • т + т

b = п - т + г₂ (2.114)

вычтем из первого уравнения второе:

а — b = (к - п) • т + (^ — г₂) (2.115) по условию

а — b • т,

Следовательно,и

(к — п) • т + (г_г — г₂) также делится на т.

Но первое слагаемое

(/с — п) • т • т, Значит, и (ту — г₂) также делится на т.

Но числа ту и г₂ могут быть лишь целыми от нуля до т — 1, что означает ^ri ^{— г}2, ^есть —(т — 1) , 0,... (т — 1).

Но среди них только одно число делится нацело на т. Это число 0.

Таким образом,

ту — г₂ = 0, (2.116)

что означает, что

п = Г₂. (2.117)

Ч.т.д.

Действия над сравнениями

Теорема 2.41

Сравнения по одному и тому же модулю можно складывать, вычитать и умножать.

Доказательство. Пусть даны два сравнения а = b(mod иг) с = d(mod т).

Докажем, что

• 1) а + с = b + d(mod тп)
• 2) а — с = b — d(mod т)
• 3) а • с = b • d(modm)
• 1) Заданные сравнения

а = b (mod ггг),

с = d (mod т). (2.118)

означают, что

а — b • т,

с — d • т. (2.119)

Рассмотрим

(а 4- с) — (b + d) = (а — Z?) + (с — г/) (2.120)

но а — b т и с — d : т.

Следовательно,

(а + с) — (b + d) : т (2.121)

то есть

а + с = b + d(mod т) (2.122)

2) Точно так же доказываем второе утверждение теоремы.

Имеем,

(а - с) - (Ь - d) = (а - Ь) - (с - d), (2.123)

Но а — b : т и с — d : т, то есть а — с и b — d сравнимы по модулю ш: а — с = b — d(mod т). (2.124)

3) Рассмотрим а • с — b • d и «добавим нолик»: b ? с — b • с.

Получаем,

а- с — b-c + b- c~b-d = c-(a — Ь) + b • (с — d) (2.125) Но

а — b : т, значит и

с • (а — Ь) • т. (2.126)

Аналогично,

с — d • т,

значит и

  Посмотреть оригинал