 |
Пункт 19. Сравнения первой степени.
|
|
|
|
В этом пункте детально рассмотрим только сравнения первой степени вида
ax º b(mod m),
оставив более высокие степени на съедение следующим пунктам. Как решать такое сравнение? Рассмотрим два случая.
Случай 1. Пусть а и m взаимно просты. Тогда несократимая дробь m/a сама просится разложиться в цепную дробь:
Эта цепная дробь, разумеется, конечна, так как m/a - рациональное число. Рассмотрим две ее последние подходящие дроби:
.
Вспоминаем (пункт 9) важное свойство числителей и знаменателей подходящих дробей: mQ n-1 -aP n-1 =(-1) n . Далее (слагаемое mQ n-1 , кратное m, можно выкинуть из левой части сравнения):
-aP n-1 º (-1) n (mod m) т.е.
aP n-1 º (-1) n-1 (mod m) т.е.
a[(-1) n-1 P n-1 b] º b(mod m)
и единственное решение исходного сравнения есть:
x º (-1) n-1 P n-1 b(mod m)
¨
Пример. Решить сравнение 111x º 75(mod 322).
Решение. (111, 322)=1. Включаем алгоритм Евклида:
322=11 · 2+100
111=100 · 1+11
100=11 · 9+1
11=1 · 11
(В равенствах подчеркнуты неполные частные.) Значит, n=4, а соответствующая цепная дробь такова:
Посчитаем числители подходящих дробей, составив для этого стандартную таблицу:
| P n |
Числитель предпоследней подходящей дроби равен 29, следовательно, готовая формула дает ответ: x º (-1) 3 × 29 × 75 º -2175 º 79(mod 322)
¨
Ох уж эти мне теоретико-числовые рассуждения из разных учебников, продиктованные традицией изложения и необходимостью обязательно использовать ранее изложенную теорию! О чем идет речь в нескольких строках выше? Дано сравнение ax º b(mod m), где a и m взаимно просты. Ну возьмите вы алгоритм Евклида, найдите те самые пресловутые u, v Î Z такие, что au+vm=1, умножьте это равенство на b: aub+vmb=b, откуда немедленно следует: aub º b(mod m). Значит решением исходного сравнения является x º ub(mod m). Собственно, и все. Поворчал.
|
|
|
Случай 2. Пусть (a,m)=d. В этом случае, для разрешимости сравнения ax º b(mod m) необходимо, чтобы d делило b, иначе сравнение вообще выполняться не может. Действительно, ax º b(mod m) бывает тогда, и только тогда, когда ax- b делится на m нацело, т.е. ax- b=t · m,
t Î Z, откуда b=ax- t × m, а правая часть последнего равенства кратна d.
Пусть b=db 1 , a=da 1 , m=dm 1 . Тогда обе части сравнения xa 1 d º b 1 d(mod m 1 d) и его модуль поделим на d:
xa 1 º b 1 (mod m 1 ),
где уже а 1 и m 1 взаимно просты. Согласно случаю 1 этого пункта, такое сравнение имеет единственное решение x 0 :
x º x 0 (mod m 1 ) (*)
По исходному модулю m, числа (*) образуют столько решений исходного сравнения, сколько чисел вида (*) содержится в полной системе вычетов: 0,1,2,..., m-2, m-1. Очевидно, что из чисел x=x 0 +t × m в полную систему наименьших неотрицательных вычетов попадают только x 0 , x 0 +m 1 , x 0 +2m 1 ,..., x 0 +(d-1)m 1 , т.е. всего d чисел. Значит у исходного сравнения имеется d решений.
Подведем итог рассмотренных случаев в виде следующей теоремы
Теорема 1. Пусть (a,m)=d. Если b не делится на d, сравнение ax º b(mod m) не имеет решений. Если b кратно d, сравнение ax º b(mod m) имеет d штук решений.
Пример. Решить сравнение 111x º 75(mod 321).
Решение. (111,321)=3, поэтому поделим сравнение и его модуль на 3:
37x º 25(mod 107) и уже (37,107)=1.
Включаем алгоритм Евклида (как обычно, подчеркнуты неполные частные):
107=37 × 2+33
37=33 × 1+4
33=4 × 8+1
4=1 × 4
Имеем n=4 и цепная дробь такова:
Таблица для нахождения числителей подходящих дробей:
| q n | |||||
| P n |
Значит, x º (-1) 3 × 26 × 25 º -650(mod 107) º -8(mod 107) º 99(mod 107).
Три решения исходного сравнения:
x º 99(mod 321), x º 206(mod 321), x º 313(mod 321),
и других решений нет.
¨
А теперь я расскажу вам одну поучительную историю. Шли по российской дороге два мальчика. Один из них засмотрелся, упал ножками в открытый канализационный люк и, (О, боже!) – сломал ручку. Второй мальчик оказался хорошим товарищем – он вытащил упавшего мальчика, вытер его, подарил ему новую шариковую ручку и сказал: " Это тебя само провидение наказало за то, что ты всегда решал сравнения первой степени только одним способом. В следующий раз поступай осмотрительнее, – выбирай наилучшую дорогу".
|
|
|
Давайте и мы, чтобы не оказаться в неприятном виде перед своими товарищами, рассмотрим пару других способов решения сравнений первой степени. Эти способы излагаются дальше в виде теорем.
Теорема 2. Пусть m>1, (a,m)=1 Тогда сравнение ax º b(mod m) имеет решение: x º ba j (m)-1 (mod m).
Доказательство. По теореме Эйлера, имеем: a j (m) º 1(mod m), следовательно, a × ba j (m)-1 º b(mod m).
¨
Пример. Решить сравнение 7x º 3(mod 10). Вычисляем:
j (10)=4; x º 3 × 7 4-1 (mod 10) º 1029(mod 10) º 9(mod 10).
Видно, что этот способ решения сравнений хорош (в смысле минимума интеллектуальных затрат на его осуществление), но может потребовать возведения числа а в довольно большую степень, что довольно трудоемко. Для того, чтобы как следует это прочувствовать, возведите самостоятельно число 24789 в степень 46728.
Теорема 3. Пусть р – простое число, 0<a<p. Тогда сравнение ax º b(mod p) имеет решение:
где C a p – биномиальный коэффициент.
Доказательство непосредственно следует из очевидного сравнения
которое нужно почленно поделить на взаимно простое с модулем число 1 × 2 × 3 ×... × a-1.
¨
Пример. Решить сравнение 7x º 2(mod 11). Вычисляем:
На этом пункт 19 можно было бы и закончить, но невозможно, говоря о решении сравнений первой степени, обойти стороной вопрос о решении систем сравнений первой степени. Дело в том, что умение решать простейшие системы сравнений не только является неотъемлемой частью общечеловеческой культуры, позволяющей гражданину не падать в ямы, расщелины и открытые люки. Такое умение, кроме всего прочего, пригодится нам при изучении сравнений произвольной степени, о которых пойдет речь в следующих пунктах.
Лемма 1 (Китайская теорема об остатках). Пусть дана простейшая система сравнений первой степени:
где m 1 ,m 2 ,...,m k попарно взаимно просты. Пусть, далее, m 1 m 2 ...m k =M s m s ; M s M s Ñ º 1(mod m s ) (Очевидно, что такое число M s Ñ всегда можно подобрать хотя бы с помощью алгоритма Евклида, т.к. (m s ,M s )=1); x 0 =M 1 M 1 Ñ b 1 +M 2 M 2 Ñ b 2 +...+M k M k Ñ b k . Тогда система (*) равносильна одному сравнению
|
|
|
x º x 0 (mod m 1 m 2 ...m k ),
т.е. набор решений (*) совпадает с набором решений сравнения x º x 0 (mod m 1 m 2 ...m k ).
Доказательство. Имеем: m s делит M j , при s ¹ j. Следовательно, x 0 º M s M s Ñ b s (mod m s ), откуда x 0 º b s (mod m s ). Это означает, что система (*) равносильна системе
которая, очевидно, в свою очередь, равносильна одному сравнению x º x 0 (mod m 1 m 2 ...m k ).
¨
Пример. Однажды средний товарищ подошел к умному товарищу и попросил его найти число, которое при делении на 4 дает в остатке 1, при делении на 5 дает в остатке 3, а при делении на 7 дает в остатке 2. Сам средний товарищ искал такое число уже две недели. Умный товарищ тут же составил систему:
которую начал решать, пользуясь леммой 1. Вот его решение:
b 1 =1; b 2 =3; b 3 =2; m 1 m 2 m 3 , т.е. M 1 =35, M 2 =28, M 3 =20.
Далее он нашел:
35 × 3 º 1(mod 4)
28 × 2 º 1(mod 5)
20 × 6 º 1(mod 7)
т.е. M 1 Ñ =3, M 2 Ñ =2, M 3 Ñ =6. Значит x 0 =35 × 3 × 1+28 × 2 × 3+20 × 6 × 2=513. После этого, по лемме 1, умный товарищ сразу получил ответ:
x º 513(mod 140) º 93(mod 140),
т.е. наименьшее положительное число, которое две недели искал средний товарищ, равно 93. Так умный товарищ в очередной раз помог среднему товарищу.
В следующей лемме, для краткости формулировки, сохранены обозначения леммы 1.
Лемма 2. Если b 1 ,b 2 ,...,b k пробегают полные системы вычетов по модулям m 1 ,m 2 ,...,m k соответственно, то x 0 пробегает полную систему вычетов по модулю m 1 m 2 ...m k .
Доказательство. Действительно, x 0 =A 1 b 1 +A 2 b 2 +...+A k b k пробегает m 1 m 2 ...m k различных значений. Покажем, что все они попарно не сравнимы по модулю m 1 m 2 ...m k .
Ну пусть оказалось, что
A 1 b 1 +A 2 b 2 +...+A k b k º A 1 b' 1 +A 2 b' 2 +...+A k b' k (mod m 1 m 2 ...m k ).
Значит,
A 1 b 1 +A 2 b 2 +...+A k b k º A 1 b' 1 +A 2 b' 2 +...+A k b' k (mod m s )
для каждого s, откуда
M s M s Ñ b s º M s M s Ñ b' s
Вспомним теперь, что M s M s Ñ º 1(mod m s ), значит M s M s Ñ º 1+m s × t, откуда (M s M s Ñ ,m s )=1. Разделив теперь обе части сравнения
|
|
|
M s M s Ñ b s º M s M s Ñ b' s
на число M s M s Ñ , взаимно простое с модулем, получим, что b s º b' s (mod m s ), т.е. b s =b' s для каждого s.
Итак, x 0 пробегает m 1 m 2 ...m k различных значений, попарно не сравнимых по модулю m 1 m 2 ...m k , т.е. полную систему вычетов.
¨
Вот теперь пункт 19 с чистой совестью закончим.
Задачки 
| 1.Reshite sravneniя:
а) 5x º 3(mod 12);
б) 256x º 179(mod 337);
в) 1215x º 560(mod 2755);
г) 1296x º 1105(mod 2413);
д) 115x º 85(mod 335).
2. Применив исконно русскую хитринку, решите систему сравнений
3. Найдите все целые числа, которые при делении на 7 дают в остатке 3, при делении на 11 дают в остатке 5, а при делении на 13 дают в остатке 4.
4. Решите систему сравнений
5. Пусть (m 1 ,m 2 )=d
Докажите, что система сравнений
имеет решения тогда и только тогда, когда b 1 º b 2 (mod d). В случае, когда система разрешима, найдите ее решения.
6. Решите систему сравнений
7. Пусть (a,m)=1, 1<a<m. Докажите, что разыскание решения сравнения ax º b(mod m) может быть сведено к разысканию решений сравнений вида b+mt º 0(mod p), где р – простой делитель числа а.
|
|
|
|
