1.2. Китайская теорема об остатках
Пусть m1, m2 , , mr числа такие что
Тогда система уравнений
i ≠ j для gcd(m.i , m j )=1
|
x = a |
|
mod m ; |
||
|
|
1 |
1 |
|
|
|
x = a2 |
mod m2 |
; |
||
|
|
|
|
|
|
|
|
|
|
||
x = ar |
mod mr |
|
|||
|
|||||
|
|
||||
имеет решение, и при этом если два числа x' системы, то они удовлетворяют уравнению
|
x' = x'' mod М |
|
|
где M = m1 m2 mr |
|
|
|
(2.6)
и x" решения данной
(2.7)
Доказательство. Докажем однозначность решения по |
mod M = m1 m2 mr |
|||
Предположим, что есть два решения системы (2.6) |
x' и |
x" . Обозначим |
||
y = x' − x" , тогдаy удовлетворяет системе |
|
|
||
y = O mod m ; |
|
|
|
|
1 |
|
|
|
|
y = O mod m2 |
; |
y = O mod M |
|
|
|
|
|
|
|
|
|
|
|
|
y = O mod mr |
|
|
|
|
|
|
|
|
|
так как m1 , m2 , ..., mr – взаимно простые. Отсюда и следует, что
|
|
|
x' = x'' mod M |
|
|
|
Покажем теперь, как сконструировать хотя бы одно решение x. |
||||||
Обозначим |
M i = |
M |
. Очевидно, что |
gcd(mi , M i )=1 |
, поэтому существует |
|
|
m |
|
|
|||
обратный элементi Ni к Mi по mod mi, т. е. Mi-1 |
= Ni- , M i Ni =1mod mi , |
|||||
который может быть найден по алгоритму Евклида для нахождения обратных элементов.
.
Обозначим |
M |
i |
= |
M |
|
|
|
i |
i |
|
|
, поэтому существует обратный |
||
|
|
mi . Очевидно, что |
|
|
|
|||||||||
|
|
|
|
|
|
|
gcd(m |
, M |
)=1 |
|
|
|||
элемент N |
к M |
по mod m , т.е. M |
-1 |
= N |
- |
, M |
i |
N |
i |
=1mod m, который может |
||||
i |
|
|
i |
i |
i |
|
i |
|
|
|
|
i |
||
быть найден по алгоритму Евклида для нахождения обратных элементов. |
||||||||||||||
Положим теперь |
|
|
|
|
|
|
|
|
|
|
||||
r |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x = ∑ai Mi N i |
mod M =( a1M1N1 +a2 M2 N2 + +ar Mr Nr )mod M |
|||||||||||||
i=1
Данное решение будет решением системы (2.6). Действительно, так
как mi делит Mj ,i ≠ j , видно, что все слагаемые будут равны нулю по mod mi, за исключением i-го слагаемого.
Тогда получаем |
x = ai M i Ni |
mod mi |
|
, и поэтому x = aimod mi, при i = 1, |
2, … , r , т.е. x – решение1 системы (2.6).
x = 2 mod 3
x = 3mod 5x = 2 mod 7
1. M = 3 5 7 =105
2. M1 =105 / 3 = 35, M2 =105 / 5 = 21, M3 =105 / 7 =15
3. N1 = 2, N2 =1, N3 =1,
4. x =( 2 35 2 +3 21 1+2 15 1) = 23mod 105
• |
Цепная дробь [a0 |
, a01, , an ] определяется как |
||||||||||
|
формальная сумма |
|
1 |
|
|
|
|
|
|
|
||
|
|
a0 |
= |
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
||
|
|
1 |
|
|
|
|
|
|
||||
|
|
|
|
a1 + |
|
|
|
|
|
|
|
|
|
|
|
|
a + |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
2 |
a |
+ |
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
a |
||||||||
|
|
|
|
|
|
n−1 |
|
|||||
|
|
|
|
|
|
|
|
n |
||||
• |
Числа a0 , a1, , ak |
k=0,1,…..,n называются неполными |
||||||||||
|
частными цепной дроби, а величины αk =[ak , ak +1, , an ] |
|||||||||||
k=0,1,…..,n называются полным частными цепной дроби.
• Числа δk =[a0 , a1, , ak ] называютсяподходящими дробями к цепной дроби