SALVETE!
КИТАЙСКАЯ
ТЕОРЕМА
ОБ ОСТАТКАХ
Как быстро определить численность войска?
Разбить на шеренги и сосчитать их количество?
А что, если солдат тысячи или даже десятки тысяч?

Теорема Сунь Цзы
Согласно легенде в Древнем Китае полководцы могли определить численность войска следующим образом: они кричали своим подданным:
«В колонну по 11 становись!», «В колонну по 13 становись!» и в каждом случае считали вовсе не количество этих колонн.
Они обращали внимание лишь на количество воинов в последнем ряду.
Но возможно ли по этим данным определить численность войска?
Конечно да.
Китайская теорема звучит примерно так.
Пусть мы делим какое-то число на другие числа.
И пусть оно не делится на них нацело.
Так вот, если делители взаимно просты, то мы точно можем сказать, какое число мы делили.
Страница трактата "Сунь Цзы Суань Цзин" китайского математика Сунь Цзы.
Занимаясь астрономией, он сформулировал данную теорему.
Зачем нужна эта теорема?
...она важнее,
чем кажется
Где применяется?
Изначально на протяжении нескольких столетий данную теорему использовали для расчета движения планет.
Китайские императоры трепетно относились к математическим расчетам и планировали свою жизнь строго в соотвествии с ними.
Сейчас это выродилось в несколько суеверные и имеющие мало общего с древностью верования типа астрологии и гороскопов.
На сегодняшний день теорема активно используется в теории чисел и высшей алгебре, но куда более примечательно ее использование для решения актуальных задач криптографии.
Теорема об остатках сильно упрощает дешифровку данных и является одним из способов нахождения уязвимостей в криптосистемах.
Алгоритм решения
Пусть мы делим какое-то число x на другие числа m₁-mₙ.
И пусть оно делится на каждый делитель с остатками b₁-bₙ.
Если делители взаимно просты, то мы точно можем сказать, какое число мы делили.
1. Проверяем, что делители взаимно просты.
2. Перемножаем между собой все делители (m₁-mₙ), полученное число назовем М.
3. Поочередно берем М и делим на каждый делитель, результат назовем М₁-Mₙ
4. Поочередно находим остаток от деления М₁ на делитель m₁, Mₙ на mₙ. Получим числа r₁-rₙ
5. Дальше для каждого числа r₁-rₙ находим множитель a₁-aₙ такой, что r₁a₁(mod m₁)=b₁
6. Теперь мы суммируем М₁a₁+...+Mₙaₙ, получаем число Z
7. Искомое нами число x=Z (mod M)
Пример
На самом деле, как бы ужасно не выглядел этот алгоритм, он очень простой и понятный.
Рассмотрим задачу:
найдите наименьшее натуральное число, дающее при делении на 2, 3, 5, 7 остатки 1, 2, 4, 6 соответственно.
Решение такой задачи найти достаточно легко - достаточно заметить, что остатки отличаются ровно на единицу от самого числа.
Что это значит?
А значит это то, что увеличив искомое число на единицу остатков бы не было.
То есть, достаточно найти НОК (2, 3, 5, 7) и отнять единицу.
Мы же рассмотрим решение через теорему об остатках.
Действуем строго по алгоритму.
Решение
1. Проверяем делители. 2, 3, 5, 7 - взаимно простые числа.
2. Умножаем делители друг на друга:
M=2*3*5*7=210
3. Поочередно делим M на делители:
М₁=M/m₁=210/2=105
М₂=M/m₂=210/3=70
М₃=M/m₃=210/5=42
М₄=M/m₄=210/7=30
4. Поочередно ищем остатки:
r₁=М₁ mod m₁=105 mod 2=1
r₂=70 mod 3 =1
r₃=42 mod 5 =2
r₄=30 mod 7 =2
5. Ищем множители:
a₁*r₁(mod m₁) =b₁
=> a₁ - такое число, которое дает при умножении на 1 и делении на 2 остаток 1;
=> a₁=1
=> a₂- такое число, которое дает при умножении на 1 и делении на 3 дает остаток 2;
=> a₂=5
=> a₃=2
=> a₄=3
5. Теперь суммируем М₁a₁+...+Mₙaₙ: Z=105*1+70*5+2*42+30*3=629
6. Находим x = Z (mod M) = 629 mod 210 = 209.
Задание 1.
Число разделили на 4, 5 и 7. В результате деления получили остатки 1, 3 и 2 соотвественно. Найдите это число.

Такая задача правильно записывается следующим образом:
x=1 (mod4)
x=3 (mod5)
x=2 (mod7)
Решение
1. Проверяем делители. 4, 5, 7 - взаимно простые числа.
2. Умножаем делители друг на друга:
M=4*5*7=140
3. Поочередно делим M на делители:
М₁=M/m₁=140/4=35
М₂=M/m₂=140/5=28
М₃=M/m₃=140/7=20
4. Поочередно ищем остатки:
r₁=М₁ mod m₁=35 mod 4=3
r₂=28 mod 5 =3
r₃=20 mod 7 =6
5. Ищем множители:
a₁*r₁(mod m₁) =b₁
=> a₁ - такое число, которое дает при умножении на 3 и делении на 4 остаток 1;
=> a₁= 3;
=> a₂=6
=> a₃=5
5. Теперь суммируем М₁a₁+...+Mₙaₙ: Z=35*3+28*6+20*5=373
6. Находим x = Z (mod M) = 373 mod 140 = 93.
Задание 2.
Артем собрал мешочек монет. Маша пересчитала их, и оказалось, что если разделить все монеты на пять равных кучек, то останется две лишние монеты. А если на четыре равные кучки — останется одна лишняя монета. В то же время монетки можно разделить на три равные кучки.
Какое наименьшее число монет могло быть у Артема?
x=2 (mod5)
x=1 (mod4)
x=0 (mod3)
Решение
1. Проверяем делители. 5, 4, 3 - взаимно простые числа.
2. Умножаем делители друг на друга:
M=4*5*3=60
3. Поочередно делим M на делители:
М₁=M/m₁=60/5=12
М₂=M/m₂=60/4=15
М₃=M/m₃=60/3=20
4. Поочередно ищем остатки:
r₁=М₁ mod m₁=12 mod 5=2
r₂=15 mod 4 =3
r₃=20 mod 3 =2
5. Ищем множители:
a₁*r₁(mod m₁) =b₁
=> a₁ - такое число, которое дает при умножении на 2 и делении на 5 остаток 2;
=> a₁= 1;
=> a₂=3
=> a₃=0
5. Теперь суммируем М₁a₁+...+Mₙaₙ: Z=12*1+15*3+20*0=57
6. Находим x = Z (mod M) = 57 mod 60 = 57.
Задание 3.
Решите:
x=13 (mod18)
x=19 (mod29)
x=12 (mod17)
Решение
1. Проверяем делители. 18, 29, 17 - взаимно простые числа.
2. Умножаем делители друг на друга:
M=18*29*17=8874
3. Поочередно делим M на делители:
М₁=M/m₁=8874/18=493
М₂=M/m₂=8874/29=306
М₃=M/m₃=8874/17=522
4. Поочередно ищем остатки:
r₁=М₁ mod m₁=493 mod 18=7
r₂=306 mod 29 =16
r₃=522 mod 17 =12
5. Ищем множители:
a₁*r₁(mod m₁) =b₁
=> a₁ - такое число, которое дает при умножении на 7 и делении на 18 остаток 13;
=> a₁= 7 (сравниваем в уме таблицу умножения 7 с числом 18, 36 и тд);
=> a₂=3
=> a₃=1
5. Теперь суммируем М₁a₁+...+Mₙaₙ: Z=493*7+306*3+522*1=4891
6. Находим x = Z (mod M) = 4891 mod 8874 = 4891.
Задание 4.
Решите:
x=8 (mod13)
x=12 (mod37)
x=11 (mod21)
Решение
1. Проверяем делители. 13, 37, 21 - взаимно простые числа.
2. Умножаем делители друг на друга:
M=13*37*21=10101
3. Поочередно делим M на делители:
М₁=M/m₁=10101/13=777
М₂=M/m₂=10101/37=273
М₃=M/m₃=10101/21=481
4. Поочередно ищем остатки:
r₁=М₁ mod m₁=777 mod 13=10
r₂=273 mod 37 =14
r₃=481 mod 21 =19
5. Ищем множители:
a₁*r₁(mod m₁) =b₁
=> a₁ - такое число, которое дает при умножении на 10 и делении на 13 остаток 8;
=> a₁= 6 (60-52=8)
=> a₂=22
=> a₃=5
5. Теперь суммируем М₁a₁+...+Mₙaₙ: Z=777*8+273*22+481*5=14627
6. Находим x = Z (mod M) = 14627 mod 10101 = 4526.
Made on
Tilda