Системы сравнений

Рассмотрим систему сравнений

Где f1(x), f2(x), …., fs(x)€Z[x].

Теорема 1. Пусть M = [m1, m2,...,ms] - наименьшее общее кратное чисел m1,m2,…,ms. Если а удовлетворяет системе (2), то и любое число из класса а по модулю М удовлетворяет этой системе.

Доказательство. Пусть b€ классу а. Так как а ≡ b(mod M), то а ≡b(mod m), i= 1,2,...,s (свойство сравнений 16). Следовательно, b, как и а, удовлетворяет каждому сравнению системы, что и доказывает теорему. Поэтому естественно считать решением системы (2) класс по модулю М.

Определение. Решением системы сравнений (2) называется класс чисел по модулю М = [m1,m2,...,ms], удовлетворяющих каждому сравнению системы.

Пример:

[6,4] = 12. Сразу заметим, что нечётные числа не удовлетворяют второму сравнению. Взяв чётные числа из полной системы вычетов по модулю 12, непосредственной проверкой убеждаемся, что 2-му сравнению удовлетворяют числа 2, -2, 6, а система имеет два решения: х ≡ 2(mod l2), х ≡ -2(mod 12).

Рассмотрим систему сравнений 1-ой степени (3)

Теорема2. Пусть d=(m1,m2), М = [m1,m2].

Если с1 — с2 не делится на d, то система (3) не имеет решений.

Если (c1 —c2):d, то система (3) имеет одно решение - класс по модулю М.

Доказательство. Из 1-го сравнения x = c1+m1t, t€Z. Подставляем во 2-е сравнение: с1+ m1t ≡ c2(mod m2) или

m1t ≡ c2-cl (mod m2). Это сравнение имеет решение только если (с2 – с1): d.

И решение представляет собой класс по модулю (теорема 4 из §2).

Пусть решение , то есть , где k€Z.

Тогда

M=[m1,m2]= , то есть x≡c1+m1t0(mod M) - решение

Примеры.

1. :2, система имеет одно решение класс по модулю 24. Из 1-го сравнения х =2+6t. Подставив вместо х во 2-е сравнение, имеем: 2 + 6t≡ 4(tnod 8); 6t≡ 2(mod 8); -2t≡2(mod8); t≡-1(mod 4); t=-1+4k; x=2+6(-1+4k); x=-4+24k, то есть x≡-4(mod 24).

2. 7-3 не делится на 3, система не имеет решений.

Следствие 1. Система сравнений (4)

Либо не имеет решений, либо имеет одно решение – класс по модулю M=[m1,…,ms].

Доказательство. Если система первых двух сравнений не имеет решений, то и (4) ие имеет решений. Если она имеет решение х ≡ a(mod[m1,m2]), то, добавив к этому сравнению третье сравнение системы, получим снова систему вида (3), которая либо имеет одно решение, либо не имеет решений. Если имеет решение, то будем так продолжить, пока не исчерпаем все сравнения системы (4). Если решение есть, то это класс по модулю М.

Замечание. Здесь использовано свойство НОК: [[m1,m2,…,m_s-1]ms]=[m1,…,ms].

Следствие 2. Если m1,m2,…,ms попарно взаимно простые, то система (4) имеет одно решение - класс по модулю M=m1m2…ms.

Пример:

Так как модули попарно взаимно простые, система имеет одно решение - класс по модулю 105 = 5*3*7. Из первого сравнения

X=2+5t, t€Z.

Подставляем во второе сравнение: 2 +5t≡ 0(mod 3) или 2t≡-2(mod3), t=-1+3k, x=2+5(-1+3k), x=-3+15k. Подставим в третье сравнение:

-3+15k≡5(mod7), 15k≡8(mod 7), k=1+7l. тогда x=-3+15(1+7l); x=12+105l; x≡12(mod 105).

Познакомимся с другим способом решения этой системы, (Используем то, что система имеет одно решение.) Умножим обе части и модуль первого сравнения на 21, второго-на 35б третьего – на 15: из суммы первого и третьего вычтем второе:

(36 —35)х ≡ 75 + 42(modl05); x≡117(mod105); x≡12(mod105).

Рассмотрим теперь систему сравнений первой степени общего вида

(5)

Если некоторое сравнение этой системы не имеет решений, то и система не имеет решений. Если же каждое сравнение системы (5) разрешимо, то решим его относительно х и получим равносильную систему вида (4):

, где (теорема 4, §2).

По следствию 1 система либо не имеет решений, либо имеет одно решение.

Пример:

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

Эта система имеет одно решение - класс по модулю 105. Умножив первое сравнение и модуль на 3, а второе на 35, получим

Вычитая из второго сравнения первое, умноженное на 11, получаем 2х ≡-62(modl05), откуда х ≡ -31(modl05).

Задачи, сводящиеся к рассмотрению системы сравнений 1-ой степени, рассматривались в арифметике китайского математика Сун Тзу, жившего примерно в начале нашей эры. У него вопрос ставился в следующей форме- найти число, дающее заданные остатки при делении на заданные числа. Он даёт и способ решения, эквивалентный следующей теореме.

Теорема (китайская теорема об остатках). Пусть m1,m2,…,ms- попарно взаимно простые числа, М = mlm2...ms, β1, β2,…, βs подобраны так, что

Тогда решение системы

будет иметь вид x≡x0(mod M).

Доказательство. Поскольку получим x0≡

Аналогичным образом проверяем, что x0≡c2(mod m2),…, x0≡cs(mod ms), то есть x0 удовлетворяет всем

сравнениям системы.

10. Сравнения 1-й степени. Неопределённые уравнения

§ 2. Сравнения 1-й степени. Неопределённые уравнения

Сравнение 1-ой степени может быть приведено к виду ax≡b(mod m).

Теорема 4. Если (a,m) = 1, то сравнение ах ≡b(mod m) (2) имеет единственное решение.

Доказательство. Возьмём 0,1,2,...,m-1 - полную систему вычетов по модулю m. Так как (а,m) = 1, то 0,а,2а,...,(m-1)а - тоже полная система вычетов (теорема 3, §2, гл 2.). В ней найдётся одно и только одно число, сравнимое с b по модулю m (принадлежащее тому же классу, что и b). Пусть это ах₀, то есть ax₀ € классу b или ax₀≡b(mod m). x ≡x₀(mod m) - единственное решение (2). Теорема доказана.

Теорема 5. Если (а, m)= 1, то решением сравнения ах≡b(mod m) является класс х₀ ≡a^φ(m)-1 b(mod m).

Доказательство. Так как (a,m) = 1, то по т. Эйлерa а^φ(m)≡1(mod m). Легко видно, что x₀≡a^φ(m)-1 b (mod m)- решение сравнения (2). Действительно,a(a^φ(m)-1b)≡a^φ(m)b≡b(mod m). Из теоремы 4 следует, что это решение единственное.

Рассмотрим методы решений сравнения ах ≡b(mod m).

1. Метод подбора. Взяв полную систему вычетов по модулю m, выбираем числа, удовлетворяющие сравнению.

2. Использование теоремы Эйлера (теорема 5).

3. Метод преобразования коэффициентов. Надо попытаться преобразовать коэффициенты так, чтобы правую часть можно было бы разделить на коэффициент при х. Преобразования, о которых идёт речь, следующие: замена коэффициентов абсолютно наименьшими вычетами, замена числа b сравнимым по модулю числом (прибавлением числа, кратного модулю) с тем, чтобы последнее делилось на а, переход от а и b к другим, сравнимым с ними числам, у которых оказался бы общий делитель и т.п. При этом пользуемся свойствами сравнений и основанными на них теоремами о равносильных сравнениях.

Примеры:

1) 223x ≡ 115(mod ll).

Сначала заменим коэффициенты наименьшими по абсолютной величине вычетами: Зх ≡ 5(mod 11). Если воспользоваться теоремой

Эйлера, то

х≡3^φ(11)-1 *5=3⁹ *5≡(3³)³*5≡(27)³*5≡5³*5≡125*5≡4*5≡9(modll).

Однако проще преобразовать коэффициенты. Заменим сравнение равносильным, прибавив к правой части число, кратное модулю:

3x ≡ 5 + 22(mod 11). Разделив обе части на число 3, взаимно простое с модулем, получим х ≡ 9(mod l1).

2) 111x≡ 8(mod 34).

Используем метод преобразования коэффициентов.

(111-3*34)x≡8(mod 34), 9x≡8+34≡42(mod 34), 3x≡14(mod 34), 3x≡14+34≡48(mod 34), x≡16(mod 34).

Теорема 6. Если (a, m) = d и b не делится на d, то сравнение (1) не имеет решений.

Доказательство (от противного). Пусть класс x₀ - решение, то есть ax₀ ≡b (mod m) или (ax₀-b):m, а, следовательно, (ax₀-b):d. Но a:d, тогда иb:d — противоречие. Следовательно, сравнение не имеет решений.

Теорема 7. Если (a,m)= d, d>1, b:d, то сравнение(1) имеет d

решений, которые составляют один класс вычетов по модулю и находится по формулам

Где с удовлетворяет вспомогательному сравнению

Замечание. Согласно теореме сравнение (1) решается следующим образом.

1) Убедившись, что (a,m) = d, d> 1 и b:d, делим обе части в сравнения (2) на d и получаем вспомогательное сравнение a₁x≡b₁ (mod m₁₎, где . Сравнение имеет единственное решение. Пусть класс с – это решение.

2) Записываем ответ x₀≡c(mod m), x₁≡c+m₁(mod m), x₂≡c+2m₁(mod m), …, x_d-1≡c+(d-1)m₁(mod m).

Доказательство. Вспомогательное сравнение по теореме 2(3) равносильно исходному сравнению (2). Так как ( 1, То вспомогательное сравнение имеет единственное решение – класс по модулю m₁= . Пусть x≡c(mod m₁) – это решение. Класс чисел с по модулю m₁ распадается на d классов по модулю m: .

Действительно, любое число из класса х0 по модулю m₁ имеет вид x₀ +m₁t. Разделим t с остатком на d: t = dq +r, где 0≤r <d. Тогда х0 + m₁t = х0 + m₁ dq + m₁ r = x0+mq + m₁ r ≡ х0+m₁r(mod m), где r= 0,1,2,...,d -1, то есть любое число из класса х0 но модулю m₁ принадлежит одному из классов, x₀, х₀ + m₁, х₀ + 2m₁,..., x0+(d-1)m₁ по модулю m. Легко видеть, что это различные классы, так как числа x0, Х0 + m1,...,X0 + (d -1)m1 отличаются друг от друга самое большее на число (d - 1)m1 < dm1=m, и этих классов d.

Итак, сравнение (1) имеет d решений по модулю m: х0, x0+m1,..., х0 +(d-1)m1.(сверху черточки горизонтальные)

Примеры.

1) 20x≡ 15(mod 108). Так как (20,108) = 4 и 15 не делится на 4, то решений нет.

2) 20x≡ 44(mod 108). (20,108) = 4 и 44:4, следовательно, сравнение имеет четыре решения. Разделив обе части и модуль на 4,получим:

5х≡11(mod 27); 5 x≡11-81 ≡ -70(mod27), х ≡ -14 ≡ 13(mod 27). Тогда х≡13 + 27r(mod 108), где г= 0,1,2,3. I jj

Ответ: x≡13(modl08); х ≡ 40(modl08); х ≡ 67(modl08); x≡94(modl08).

Применение теории сравнений к решению неопределённых уравнении

Рассмотрим неопределённое или, как его иначе называют, Диофантово уравнение первой степени с двумя неизвестными ах + by = с, где a,b,c€Z. Требуется решить это уравнение в целых числах. Если (a,b)=d и с не делится на d, то очевидно, чТО сравнение не имеет решений в целых числах. Если же с делится на d, ТО поделим обе части уравнения на d. Поэтому достаточно рассмотреть случай, когда (а, b) =1.

Так как ах отличается от с на число, кратное b, то ах ≡ c(mod b) (без ограничения общности можно считать, что b > 0). Решая это сравнение, получим х ≡x1 (mod b) или x=x1+bt, где t€Z. Для определения Соответствующих значений у имеем уравнение а(х1 + bt) + by = с, откуда

Причём -целое число, оно является частным значением неизвестного y, соответствующим x1(получается, как и x1, при t=0). А общее решение уравнения примет вид систему уравнений x=x1+bt, y=y1-at, где t- любое целое число.

Заметим, что 1) уравнение ах + by = с можно было решать, начав со сравнения by ≡ c(mod а), так как by отличается от с на число, кратное а;

2)в качестве модуля удобнее выбирать наименьший из модулей а и b.

Пример, 50x – 42y= 34.

Разделим обе части уравнения на 2.

25х-21у=17;

25х ≡ 17(mod2l); 4х ≡ 17 (mod 21) или 4х ≡ 17-21 ≡ -4(mod21).

х ≡ -1 (mod 21), то есть x=-1+21t, t€Z. Подставим найденное х в уравнение. 25(-1 + 21t)- 21y= 17; 21у =-42 + 25* 21t и у =-2 + 25t.

ИТАК: где t€Z