§4. Теория сравнений

---

Пункт 21. Сравнения любой степени по составному модулю.

Переход от решения сравнений по простому модулю к a priori более сложной задаче — решению сравнений по составному модулю (переход от пункта 20 к пункту 21) осуществляется быстро и без лишних затей с помощью следующей теоремы:

Теорема 1. Если числа m ₁ , m ₂ ,… m _k попарно взаимно просты, то сравнение f ( x ) є 0(mod m ₁ m ₂ … m _k ) равносильно системе сравнений:

При этом, если Т ₁ , Т ₂ , ..., Т _к  — числа решений отдельных сравнений этой системы по соответствующим модулям, то число решений Т исходного сравнения равно Т ₁ Т ₂ ...Т _к .

Доказательство. Первое утверждение теоремы (о равносильности системы и сравнения) очевидно, т.к. если a є b (mod m ) , то a є b (mod d ), где d делит m . Если же a є b (mod m ₁ ) и a є b (mod m ₂ ), то a є b (mod HOK ( m ₁ , m ₂ )), где НОК ( m ₁ ,  m ₂ )– наименьшее общее кратное m ₁ и m ₂ . (Вспомните простейшие свойства сравнений из пункта 16).

Обратимся ко второму утверждению теоремы (о числе решений сравнения).

Каждое сравнение f ( x ) є 0(mod m _s ) выполняется тогда и только тогда, когда выполняется одно из T _s штук сравнений вида x є b _s (mod m _s ), где b _s пробегает вычеты решений сравнения f ( x ) є 0(mod m _s ). Всего различных комбинаций таких простейших сравнений

Т ₁ Т ₂ ...Т _к штук. Все эти комбинации, по лемме 2 из пункта 19, приводят к различным классам вычетов по mod( m ₁ m ₂ … 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 ₁ (mod p ) – какое-нибудь решение сравнения f ( x ) є 0(mod p ). Это означает, что

x = x ₁ + p Ч t ₁ , где t ₁ О Z .

Вставим это х в сравнение f ( x ) є 0(mod p ² ). Получим сравнение

f ( x ₁ + p Ч t ₁ ) є 0(mod p ² ),

которое тоже, очевидно, выполняется.

Разложим далее (не пугайтесь!) левую часть полученного сравнения по формуле Тейлора по степеням ( х - х ₁ ):

Но, ведь, x = x ₁ + p Ч t ₁ , следовательно,

.

Заметим, что число f ^{( k )} ( x ₁ )/ k ! всегда целое, т.к. f ( x ₁ + p Ч t ₁ ) — многочлен с целыми коэффициентами. Теперь в сравнении

f ( x ₁ + p Ч t ₁ ) є 0(mod p ² )

можно слева отбросить члены, кратные р ² :

.

Разделим последнее сравнение и его модуль на р :

.

Заметим, опять, что f ( x ₁ )/ p  — целое число, т.к. f ( x ₁ ) є 0(mod p ). Далее ограничимся случаем, когда значение производной f ў ( x ₁ ) не делится на р . В этом случае имеется всего одно решение сравнения первой степени

относительно t ₁ :

t ₁ є t ₁ ^С (mod p ).

Это, опять-таки, означает, что t ₁ = t ₁ ^С + p Ч t ₂ , где t ₂ О Z , и

.

Снова вставим это x = x ₂ + p ² t ₂ в сравнение f ( x ) є 0(mod p ³ ) (но теперь это сравнение уже по mod p ³ , разложим его левую часть по формуле Тейлора по степеням ( х-х ₂ ) и отбросим члены, кратные p ³ :

f ( x ₂ ) +( f ў ( x ₂ )/1!) Ч p ² t ₂ є 0(mod p ³ ).

Делим это сравнение и его модуль на р ² :

f ( x ₂ )/ p ² + f ў ( x ₂ ) Ч t ₂ є 0(mod p ).

Опять-таки f ( x ₂ )/ p ²  — целое число, ведь число t ₁ ^С такое, что f ( x ₁ + p Ч t ₁ ^С ) є 0(mod p ² ). Кроме того, x ₂ є x ₁ (mod p ), значит f ў ( x ₂ ) є f ў ( x ₁ )(mod p ), т.е. f ў ( x ₂ ), как и f ў ( x ₁ ), не делится на р . Имеем единственное решение сравнения первой степени f ( x ₂ )/ p ² + f ў ( x ₂ ) Ч t ₂ ) є 0(mod p ) относительно t ₂ :

t ₂ є t ₂ ^С (mod p ).

Это, опять-таки, означает, что t ₂ = t ₂ ^С + p Ч t ₃ , где t ₃ О Z , и

и процесс продолжается дальше и дальше, аналогично предыдущим шагам, до достижения степени p ^a , в которой стоит простое число р в модуле исходного сравнения f ( x ) є 0(mod p ^a ).

Итак:

Всякое решение x є x ₁ (mod p ) сравнения f ( x ) є 0(mod p ), при условии p/ f ў ў ( x ₁ ), дает одно решение сравнения f ( x ) є 0(mod p ^a ) вида x є x _a + p ^a t _a , т.е. x є x _a (mod p ^a ).

Ё

Пример. Решить сравнение x ⁴ +7 x +4 є 0(mod27).

Решение. Весь богатейший педагогический опыт, накопленный человечеством к моменту написания этой книжки, показывает, что наиболее одаренные ученики в состоянии догадаться без посторонней помощи, что 27=3 ³ . Далее, получив небольшую подсказку в форме бодрящей мимики и вскриков преподавателя, ученики обычно оказываются в состоянии проверить перебором полной системы вычетов по mod3, что сравнение x ⁴ +7 x +4 є 0(mod3) имеет всего одно решение x є 1(mod3). По поводу дальнейших возможностей учеников ничего определенного спрогнозировать нельзя, но последующий процесс решения, в идеале, должен быть таким:

f ў ( x )=(4 x ³ +7) Ѕ _{x є 1} є 2(mod3),

т.е. не делится на р = 3. Далее:

x ₁ =1+3 Ч t ₁

f (1)+ f ў (1) 3 Ч t ₁ є 0(mod3 ² )

Ищем t ₁ :

3+3 t ₁ Ч 2 є 0(mod9),

после деления на р =3:

1+2 t ₁ є 0(mod3),

t ₁ є 1(mod3)

- единственное решение. Далее:

t ₁ =1+3 t ₂ ,

x =1+3 t ₁ =4+9 t ₂ ,

f (4)+9 Ч t ₂ Ч f ў (4) є 0(mod p ³ =27),

18+9 Ч 20 Ч t ₂ є 0(mod27),

и, после деления на p ² =9, ищем t ₂ :

2+20 t ₂ є 0(mod3),

t ₂ є 2(mod3),

t ₂ =2+3 t ₃ ,

откуда

x =4+9 Ч (2+3 t ₃ )=22+27 t ₃ .

Значит, единственным решением исходного сравнения является x є 22(mod27).

Ё

Следующая теорема относится к специфическому, но весьма приятному виду сравнений.

Теорема 2. Пусть A , m , n - натуральные числа; ( A , m )=1 ,

x є x ₀ (mod m ) — одно из решений сравнения

x ⁿ є A (mod m ).

Тогда все решения этого сравнения получаются умножением x ₀ на вычеты решений сравнения y ⁿ є 1(mod m ).

Доказательство. Перемножим сравнения:

откуда видно, что x ₀ y  — решения сравнения x ⁿ є A (mod m ).

Если теперь , то . Действительно, предположим, что x ₀ y ₁ є x ₀ y ₂ (mod m ). Очевидно, что ( x ₀ , m )=1, т.к. иначе было бы:

x ₀ = d Ч x ₀ ^С , m = d Ч m ^С ,

x ₀ = d ⁿ ( x ₀ ^С ) ⁿ є A (mod d m ^С ),

cледовательно d делит А и делит m , что противоречит взаимной простоте А и m . Значит ( x ₀ , m )=1 и сравнение x ₀ y ₁ є x ₀ y ₂ (mod m )

можно поделить на x ₀ : y ₁ є y ₂ (mod m ) — а это противоречит исходному предположению. Таким образом, для разных y ₁ и y ₂ , получаются разные решения.

Осталось убедиться, что каждое решение сравнения x ⁿ є A (mod m ) получается именно таким способом. Имеем:

x ⁿ є A (mod m )

x ₀ ⁿ є A (mod m ),

следовательно, x ⁿ є x ₀ ⁿ (mod m ). Возьмем число y такое, что x є y Ч x ₀ (mod m ). Тогда y ⁿ x ₀ ⁿ є x ₀ ⁿ (mod m ), т.е. y ⁿ є 1(mod m ).

Ё

Пункт с номером 21 (очко!) закончен.

Задачки

1. Сколько решений имеет сравнение x 5 + x +1 є 0(mod105) ? 2. Решите сравнения: а) 7 x 4 +19 x +25 є 0(mod27); б) 9 x 2 +29 x +62 є 0(mod64); в) 6 x 3 +27 x 2 +17 x +20 є 0(mod30); г) 31 x 4 +57 x 3 +96 x +191 є 0(mod225); д) x 3 +2 x +2 є 0(mod125); е) x 4 +4 x 3 +2 x 2 +2 x +12 є 0(mod625).

NS	НОВОСТИ КУЛЬТУРЫ
Всем известно, что курение мешает занятиям спортом. Ученые установили, что, в свою очередь, занятия спортом не дают по-человечески покурить. Новости микрохирургии. Опять потерялся микрохирург Петров.