Китайская теорема об остатках

Поднебесная 3 века подарила теории чисел одну любопытную теорему, о коей пойдет речь в сей статье.

По легенде, для того, чтобы посчитать, сколько солдат вернулось из сражения, их просили вставать в шеренгу по 11, по 13, по 17… и смотрели на последнюю колонну, сколько там оставалось бравых китайцев. И по остаткам однозначно определяли искомое количество.

Поясним на примере. При делении 26 на 7 получается остаток 5, при делении на 6 – 2. Китайская теорема об остатках утверждает, что 26 – это единственное число среди первых 42 (потому что 6*7=42), которое при делении на 6 и 7 имеет в остатке 2 и 5. И вот китайские солдатосчеты находили такое число, которое при делении на некоторые взаимнопростые (это важно!!!) числа имели определенные остатки. (Ну, супом воинов тоже кормить можно, но так круче. И точнее.)

Как это делается. Пусть вам дана система сравнений:Наша задача – найти, с чем сравним x по модулю M (M – произведение всех m). И это:

\[ a=a_1*M/m_1 *μ_1+a_2*M/m_2 *μ_2+⋯+a_n*M/m_n *μ_n \]

Почему? Давайте посмотрим на первое слагаемое. Оно делится на все m, кроме первого, и поэтому совершенно не влияет на них (потому что M/m – произведение всех m, кроме той m, которую мы рассматриваем). И еще первое слагаемое сравнимо с a по модулю m первое. Почему? Вся фишка в том, что такое μ. Это мультипликативное обратное по модулю (вы умножаете что-то на его мультипликативное обратное и получаете 1). Любопытный читатель докажет его существование и единственность и узнает, что такое расширенный алгоритм Евклида. А мы пока продолжим. Наше μ – обратное для M/m по модулю m. То есть произведение (M/m)*μ сравнимо с 1. В таком случае a*(M/m)*μ сравнимо с a по модулю m! Таким образом, очередное слагаемое определяет остаток при делении только для одного m. Вот и все!

Призываю к практике и экспериментам! Начнем с поиска мультипликативного обратного по модулю. К примеру, на что надо умножить 7, чтобы произведение было сравнимо с 1 по модулю 9? Ну а после решения нескольких подобных задач придумайте систему сравнений и решите ее!

И если вы еще не читали эту статью об ошибках не по невнимательности, то вперед!

Поделиться постом
Have your say!
0 0
1 Comment

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>