ас = (nip + nq + Ir) р + rq, bd = {msp + mq + sr)p + rq.

Из совпадения остатков a± с и Ь ± d, а также ас и bd следует справедливость сформулированной теоремы.

•Для удобства записи остаток от деления натурального числа X на .натуральное число р будем обозначать как rest -.

Из доказанной теоремы следует, что сравнения можно почленно складывать, вычитать и - умножать, ожно также переносить члены сравнения из одной части сравнения в другую с изменением знака, умножать обе части сравнения на одну и ту же константу и возводить обе части сравнения в одинаковую степень. Все эти преобразования для сравнений являются равносильными, т. е. сохраняют справедливость срав-jieHHH.

Пример 6.1. Для данной тройки сравнений 6 = 30(mod4), tl=25(mod4) и О = 44(mod4) найти сумму и произведение сравнений, понимая под суммой и произведением сравнений операции, определенные в теореме 6.1.

Производя почленное суммирование левых и правых частей сравнений и почленное перемножение левых и правых частей сравнений, получим 7 = 79 (mod 4) и 0 = 33000 (mod 4).

♦ Теорема 6.2. Если кисла, образующие сравнение, и модуль разделить на одно и то же число, являющееся их общим делителем, пю сравнение останется справедливым.

Доказательство. Из того, что а = 6(mod/?), следует аЬ -\- пр. Пусть h является общим делителем а, b и р. Тогда а = а,Л, Ь = ЬЬир= ph. Отсюда a-h = bh -Ь nph. Или = fe, + пр. Но последнее эквивалентно выполнению сравнения ъш\а,1щЬ(тойр. Теорема доказана.

Аналогично можно показать, что обе части сравнения и модуль можно умножить на одно и то же число.

Теорема 6.3. Обе части сравнения можно разделить на одно и то же число, являющееся их общим делителем, если оно является взаимно простым с модулем сравнения.

Доказательство. Справедливость этого вытекает из следующих рассуждений. Из того, что аЬ (mod р) и h есть общий делитель an Ь, вытекает, что afi = bfi (mod р). Перенося правую часть сравнения в левую сторону, получим а - Ь = 0 (modр). Но по условию h взаимно просто с р я, следовательно, h на р не делится нацело. Отсюда следует, что а, - 6, делится нацело на р. Тогда а = пр q bi = mp -\- q. Отсюда ai = biimodp). Теорема доказана.

Докажем, наконец, еще одну теорему, относящуюся к теории сравнений.

Теорема 6.4. Если сравнение а = Ь (mod р) справедливо для 11=Pi, р2 , Рд, то справедливо сравнение а = Ь (mod р), -где р есть наименьигее общее кратное чисел pi, /?2,... рд.

Доказательство. Из того, что справедливы сравнения а=Ь (mod/?,), a=b (modр), ..., a=b (modPg), вытекает (см. предыдущую теорему), что разность а~Ь делится на все числа Pi, р2,... , Рд. Из этого, как это известно из курса арифметики, вытекает, что а - b делится на наименьшее общее кратное этих чисел, что эквивалентно справедливости сравнения

а = Ь (mod р).

Пусть теперь число х удовлетворяет следующей системе сравнений л = а, (mod/?,), х = а2 (modР2),..., х = ag(modPg) и пусть значение х нам неизвестно. Для нахождения класса чисел, удовлетворяющих данной системе сравнений, поступим следующим образом. Вместо сравнений напишем эквивалентные им равенства

x=miPi-{-ai

х = т2р2 + CI2 .

Х = тдРд + ад

Так как левые части этих равенств одинаковы, то, можно приравнять правые части равенств

-Ь а, = ОТ2Р2 + «2 = ••• гпдрд + а д.

Б-79.-18 273

Преобразуем первое из полученных уравнений как /игРа + Дг -aii Так как /Wi является целым числом. Pi

то значения т, должны быть выбраны так, чтобы выражение "гРг + «г - я, целым. Используя Р\

уравнение mjy-Jramp+a, получим другое условие на щ и т. д. Совокупность этих условий позволит выразить вид чисел щ.

Пример 6.2. По системе сравнений

jc = 3 (mod 8), , = л: = 5 (mod 7),

j,. a;=l(mod2)

найти вид чисел л:.

• Из понятия сравнения вытекает, что л; = 8т + 3, л: = 7я + 5 и jc = 2г + 2. Приравнивая правые части равенств, - получим

8т + 3 = 7й + 5 = 2г+1.

Отсюда

„ л , н 7п + 2

8

Необходимо подобрать такое значение п, при котором т и г являются целыми. Для данного примера такими значениями п будут все значения вида 8к + 2, где k = 0, 1, 2,...

Пусть мы имеем множество натуральных чисел N. Выберем некоторый модуль р и для каждого числа из найдем остаток от деления его на р. Число различных остатков равно р (от О до р- 1). Все множество Л разбивается при этом на р непересекающихся классов, в каждый из которых входят все числа, сравнимые между собой по модулю р. Эти классы называются остатючными классами.

Если одно и то же число х делится на несколько модулей pi, Р2, ... Рд, то число остаточных классов, на которые, разбивается множество Л, равно произ-д

ведению модулей П Pi- Последнее утверждение верно =1

лишь при условии, что всё модули Pi являются взаимно простыми числами, т. е. появление того или иного