Переход от решения сравнений по простому модулю к a priori более сложной задаче — решению сравнений по составному модулю (переход от пункта 20 к пункту 21) осуществляется быстро и без лишних затей с помощью следующей теоремы:
Теорема 1. Если числа m 1 , m 2 ,… m k попарно взаимно просты, то сравнение f ( x ) є 0(mod m 1 m 2 … m k ) равносильно системе сравнений:
При этом, если Т 1 , Т 2 , ..., Т к — числа решений отдельных сравнений этой системы по соответствующим модулям, то число решений Т исходного сравнения равно Т 1 Т 2 ...Т к .
Доказательство. Первое утверждение теоремы (о равносильности системы и сравнения) очевидно, т.к. если a є b (mod m ) , то a є b (mod d ), где d делит m . Если же a є b (mod m 1 ) и a є b (mod m 2 ), то a є b (mod HOK ( m 1 , m 2 )), где НОК ( m 1 , m 2 )– наименьшее общее кратное m 1 и m 2 . (Вспомните простейшие свойства сравнений из пункта 16).
Обратимся ко второму утверждению теоремы (о числе решений сравнения).
Каждое сравнение f ( x ) є 0(mod m s ) выполняется тогда и только тогда, когда выполняется одно из T s штук сравнений вида x є b s (mod m s ), где b s пробегает вычеты решений сравнения f ( x ) є 0(mod m s ). Всего различных комбинаций таких простейших сравнений
Т 1 Т 2 ...Т к штук. Все эти комбинации, по лемме 2 из пункта 19, приводят к различным классам вычетов по mod( m 1 m 2 … m k ).
Ё
Итак, решение сравнения
сводится к решению сравнений вида
f
(
x
)
є
0(mod
p
a
). Оказывается, что решение этого последнего сравнения, в свою очередь,
сводится к решению некоторого сравнения
g
(
x
)
є
0(mod
p
) c другим многочленом в левой части, но уже с простым модулем, а это, просто
напросто, приводит нас в рамки предыдущего пункта. Сейчас я расскажу процесс
сведения решения сравнения
f
(
x
)
є
0(mod
p
a
) к решению сравнения
g
(
x
)
є
0(mod
p
).
Процесс сведения.
Очевидно, выполнение сравнения f ( x ) є 0(mod p a ) влечет, что х подходит в сравнение f ( x ) є 0(mod p ). Пусть x є x 1 (mod p ) – какое-нибудь решение сравнения f ( x ) є 0(mod p ). Это означает, что
x = x 1 + p Ч t 1 , где t 1 О Z .
Вставим это х в сравнение f ( x ) є 0(mod p 2 ). Получим сравнение
f ( x 1 + p Ч t 1 ) є 0(mod p 2 ),
которое тоже, очевидно, выполняется.
Разложим далее (не пугайтесь!) левую часть полученного сравнения по формуле Тейлора по степеням ( х - х 1 ):
Но, ведь, x = x 1 + p Ч t 1 , следовательно,
.
Заметим, что число f ( k ) ( x 1 )/ k ! всегда целое, т.к. f ( x 1 + p Ч t 1 ) — многочлен с целыми коэффициентами. Теперь в сравнении
f ( x 1 + p Ч t 1 ) є 0(mod p 2 )
можно слева отбросить члены, кратные р 2 :
.
Разделим последнее сравнение и его модуль на р :
.
Заметим, опять, что f ( x 1 )/ p — целое число, т.к. f ( x 1 ) є 0(mod p ). Далее ограничимся случаем, когда значение производной f ў ( x 1 ) не делится на р . В этом случае имеется всего одно решение сравнения первой степени
относительно
t
1
:
t 1 є t 1 С (mod p ).
Это, опять-таки, означает, что t 1 = t 1 С + p Ч t 2 , где t 2 О Z , и
.
Снова вставим это x = x 2 + p 2 t 2 в сравнение f ( x ) є 0(mod p 3 ) (но теперь это сравнение уже по mod p 3 , разложим его левую часть по формуле Тейлора по степеням ( х-х 2 ) и отбросим члены, кратные p 3 :
f ( x 2 ) +( f ў ( x 2 )/1!) Ч p 2 t 2 є 0(mod p 3 ).
Делим это сравнение и его модуль на р 2 :
f ( x 2 )/ p 2 + f ў ( x 2 ) Ч t 2 є 0(mod p ).
Опять-таки f ( x 2 )/ p 2 — целое число, ведь число t 1 С такое, что f ( x 1 + p Ч t 1 С ) є 0(mod p 2 ). Кроме того, x 2 є x 1 (mod p ), значит f ў ( x 2 ) є f ў ( x 1 )(mod p ), т.е. f ў ( x 2 ), как и f ў ( x 1 ), не делится на р . Имеем единственное решение сравнения первой степени f ( x 2 )/ p 2 + f ў ( x 2 ) Ч t 2 ) є 0(mod p ) относительно t 2 :
t 2 є t 2 С (mod p ).
Это, опять-таки, означает, что t 2 = t 2 С + p Ч t 3 , где t 3 О Z , и
и процесс продолжается дальше и дальше, аналогично предыдущим шагам, до достижения степени p a , в которой стоит простое число р в модуле исходного сравнения f ( x ) є 0(mod p a ).
Итак:
Всякое решение x є x 1 (mod p ) сравнения f ( x ) є 0(mod p ), при условии p/ f ў ў ( x 1 ), дает одно решение сравнения f ( x ) є 0(mod p a ) вида x є x a + p a t a , т.е. x є x a (mod p a ).
Ё
Пример. Решить сравнение x 4 +7 x +4 є 0(mod27).
Решение. Весь богатейший педагогический опыт, накопленный человечеством к моменту написания этой книжки, показывает, что наиболее одаренные ученики в состоянии догадаться без посторонней помощи, что 27=3 3 . Далее, получив небольшую подсказку в форме бодрящей мимики и вскриков преподавателя, ученики обычно оказываются в состоянии проверить перебором полной системы вычетов по mod3, что сравнение x 4 +7 x +4 є 0(mod3) имеет всего одно решение x є 1(mod3). По поводу дальнейших возможностей учеников ничего определенного спрогнозировать нельзя, но последующий процесс решения, в идеале, должен быть таким:
f ў ( x )=(4 x 3 +7) Ѕ x є 1 є 2(mod3),
т.е. не делится на р = 3. Далее:
x 1 =1+3 Ч t 1
f (1)+ f ў (1) 3 Ч t 1 є 0(mod3 2 )
Ищем t 1 :
3+3 t 1 Ч 2 є 0(mod9),
после деления на р =3:
1+2 t 1 є 0(mod3),
t 1 є 1(mod3)
- единственное решение. Далее:
t 1 =1+3 t 2 ,
x =1+3 t 1 =4+9 t 2 ,
f (4)+9 Ч t 2 Ч f ў (4) є 0(mod p 3 =27),
18+9 Ч 20 Ч t 2 є 0(mod27),
и, после деления на p 2 =9, ищем t 2 :
2+20 t 2 є 0(mod3),
t 2 є 2(mod3),
t 2 =2+3 t 3 ,
откуда
x =4+9 Ч (2+3 t 3 )=22+27 t 3 .
Значит, единственным решением исходного сравнения является x є 22(mod27).
Ё
Следующая теорема относится к специфическому, но весьма приятному виду сравнений.
Теорема 2. Пусть A , m , n - натуральные числа; ( A , m )=1 ,
x є x 0 (mod m ) — одно из решений сравнения
x n є A (mod m ).
Тогда все решения этого сравнения получаются умножением x 0 на вычеты решений сравнения y n є 1(mod m ).
Доказательство. Перемножим сравнения:
откуда видно, что x 0 y — решения сравнения x n є A (mod m ).
Если теперь
, то
. Действительно, предположим, что
x
0
y
1
є
x
0
y
2
(mod
m
). Очевидно, что (
x
0
,
m
)=1, т.к. иначе было бы:
x 0 = d Ч x 0 С , m = d Ч m С ,
x 0 = d n ( x 0 С ) n є A (mod d m С ),
cледовательно d делит А и делит m , что противоречит взаимной простоте А и m . Значит ( x 0 , m )=1 и сравнение x 0 y 1 є x 0 y 2 (mod m )
можно поделить на x 0 : y 1 є y 2 (mod m ) — а это противоречит исходному предположению. Таким образом, для разных y 1 и y 2 , получаются разные решения.
Осталось убедиться, что каждое решение сравнения x n є A (mod m ) получается именно таким способом. Имеем:
x n є A (mod m )
x 0 n є A (mod m ),
следовательно, x n є x 0 n (mod m ). Возьмем число y такое, что x є y Ч x 0 (mod m ). Тогда y n x 0 n є x 0 n (mod m ), т.е. y n є 1(mod m ).
Ё
Пункт с номером 21 (очко!) закончен.
Задачки
![]() |
1. Сколько решений имеет сравнение x 5 + x +1 є 0(mod105) ?
2.
Решите сравнения:
|
NS | НОВОСТИ КУЛЬТУРЫ |
Всем известно, что курение мешает занятиям спортом. Ученые установили, что, в свою очередь, занятия спортом не дают по-человечески покурить. Новости микрохирургии. Опять потерялся микрохирург Петров. |