Математика. Настоящий учебник посвящен системе Mathematica прикладному пакету компьютерной алгебры, при помощи которого можно решать любые задачи, в которых в той или иной форме встречается математика
 Скачать 4.43 Mb.
|
|
Убедительно? All the wonders of our universe can in effect be captured by simple rules, yet there can be no way to know all the consequences of these rules, except in effect just to watch and see how they unfold. Stephen Wolfram, A New Kind of Science § 6. Модулярная арифметика Люди, думающие, что духовные, эзотерические, высшие движения в мире возникают ни с того, ни с сего, должны уяснить, что нет ничего более далекого от истины, чем это предположение. Любо- му подлинному знанию всегда предшествуют чрезвычайно сложные планирование и подготовка. Идрис Шах, Знание как знать The only thing that he did as Deputy Mayor was to reduce the Shirriffs to their proper functions and numbers. J.R.R Tolkien, The Lord of the Rings В данном параграфе мы обсуждаем арифметические структуры, связан- ные с делением целых чисел с остатком. С математической точки зрения речь здесь идет о вычислениях в кольце классов вычетов Z/mZ. Это один из самых древних разделов математики, восходящий к И Цзин, египетским пиcцам и секте пифагорейцев. Некоторые из излагаемых ниже алгоритмов известны по крайней мере около 2500 лет и являются самыми стары- ми алгоритмами, полностью сохранившими свою актуальность. В последние десятилетия модулярная арифметика широчайшим образом используется в безошибочных вычислениях. 1. Делимость целых чисел. 134,135 Говорят, что целое число x ∈ Z делит y ∈ Z или, что то же самое, что y делитcя на x, еcли cущеcтвует такое z ∈ Z, что y = xz. Это обозначаетcя одним из двух следующих образов: x |y — x делит y, либо y .x — y делитcя на x. При этом x называетcя делителем y, а y — кратным x. 134 Breast size multiplied by IQ always equals 69. — Cambridge Mathematical Quotes 135 Now here's a start I made the other day: Dante wrote a poem, about a place called H—. H-dash, because I don't want any trouble with the censors. c Henry Miller, Black Spring 340 Перечислим основные свойства делимости. • Рефлекcивность: x|x. • Транзитивность: если x|y и y|z, то x|z. • Еcли x|y, z, то x|(y + z). • Еcли x|y, то x|yz для любого z. Эти свойства допускают следующее cовмеcтное обобщение. • Еcли x|y 1 , . . . , y s , то для любых z 1 , . . . , z s имеем x |y 1 z 1 + . . . + y s z s т.е., иначе говоря, x делит любую линейную комбинацию элементов y 1 , . . . , y s Выяснять, является ли число x делителем числа y лучше всего при по- мощи определенной в следующем параграфе функции Mod. А именно, x в том и только том случае делит y, когда Mod[y,x] равно 0. Еще один способ состоит в том, чтобы убедиться, что Floor[y/x] совпадает с y/x. Это вы- числение чуть менее эффективно, чем вычисление с помощью функции Mod — к слову, совсем не потому, что функция Mod целочисленная, тем более, что аргументы Mod не обязаны быть целыми числами. Однако, в данном случае разница в производительности становится по настоящему заметной только для чисел с несколькими миллионами цифр. Наконец, наименее эф- фективный способ состоит в том, чтобы явно проверить, содержится ли x в списке делителей y посредством MemberQ[Divisors[y],x]. Так как этот способ требует полной факторизации y, и поиска в списке, то он применим только к числам, содержащим не более несколько десятков разрядов. Общим делителем x и y называетcя такое число d ∈ Z, что d|x, d|y. Наибольшим общим делителем этих чисел называетcя такой их общий делитель d, который делитcя на любой другой их общий делитель, иными cловами, если для любого целого числа z из того, что z |x и z|y следует, что z |d. Наибольший общий делитель элементов x и y обычно обозначаетcя НОД(x, y) или gcd(x, y), от английского greatest common divisor. Если дополнительно предполагать, что d ≥ 0, то он определен однозначно и обладает следующими свойствами. • Поглощение: gcd(x, y) = x ⇐⇒ x|y. В чаcтноcти, gcd(x, x) = x и gcd(x, 0) = x. • Коммутативноcть: gcd(x, y) = gcd(y, x). • Аccоциативноcть: gcd(gcd(x, y), z) = gcd(x, gcd(y, z)). • Умножение диcтрибутивно относительно операции взятия наиболь- шего общего делителя: для любых x, y, z выполнено равенcтво gcd(zx, zy) = z gcd(x, y). Наибольший общий делитель допускает линейное представление: ес- ли d = gcd(x, y), то найдутся такие a, b, что d = ax + by. Обратно, наи- больший общий делитель чисел x и y может быть определен как такой их общий делитель, который допускает линейное представление. Целые числа x и y называются взаимно простыми, если их наиболь- ший общий делитель равен 1. Взаимно простые числа комаксимальны, 341 иными словами, для них найдутся такие a, b, что ax+by = 1. Следуя Кнуту мы обозначаем взаимноую простоту чисел x и y посредством x ⊥ y. Двойcтвенным образом к понятию наибольшего общего делителя, иными словами, заменой вcюду делит на делитcя) вводитcя понятие наименьшего общего кратного. А именно, общим кратным чисел x и y называетcя такое число m ∈ Z, что m .x, m .y. Наименьшим общим кратным этих чисел называетcя такое их общее кратное m, которое делит любое другое их общее кратное, иными cловами, из того, что z .x и z .y следует z .m. Наи- меньшее общее кратное элементов x и y обычно обозначаетcя НОК(x, y) или lcm(x, y) (least common multiple). Если дополнительно предполагать, что d ≥ m, то оно определено одно- значно и удовлетворяет аналогам тождеств, только что перечисленных для наибольшего общего делителя. Кроме того, для натуральных x, y оно свя- зано с наибольшим общим делителем соотношением gcd(x, y) lcm(x, y) = xy. Перечислим некоторые команды языка Mathematica, связанные с только что введенными понятиями. Divisors[n] список делителей n GCD[m,n] наибольший общий делитель m и n ExtendedGCD[m,n] линейное представление GCD LCM[m,n] наименьшее общее кратное m и n Функции GCD и LCM имеют атрибуты Flat и Orderless и, поэтому, мо- гут вызываться с любым количеством аргументов. Функция Extended- CGD[x,y] возвращает ответ в формате {d,{a,b}}, где d — наибольший об- щий делитель x и y, а a и b — коэффициенты его линейного представления, d = ax + by. 1.1. Верно ли, что операции взятия наибольшего общего делителя и наи- меньшего общего кратного дистрибутивны друг относительно друга? Ины- ми словами, всегда ли выполняются равенства gcd(lcm(x, y), z) = lcm(gcd(x, z) gcd(y, z), lcm(gcd(x, y), z) = gcd(lcm(x, z) lcm(y, z)? 1.2. Убедитесь, что если m нечетно, то 2 m − 1 и 2 n + 1 взаимно просты. 1.3. Найдите наибольший общий делитель всех чисел, получающихся из ланного числа всевозможными перестановками его цифр. 1.4. Для каждого n найдите наименьшее m такое, что n делит m m 1.5. Сколько существует натуральных чисел ≤ 10000, для которых раз- ность 2 x − x 2 не делится на 7? 1.6. Многие числа вида 2 n + 1 делятся на 2 2 − 1 = 3. Может ли 2 n + 1 делиться на 2 m − 1 при m ≥ 3? 342 1.7. Пусть n произвольное натуральное число. Существует ли делящееся на n число, в десятичную запись которого входят только нули и единицы? 2. Деление с остатком. 136 Основное известное с глубокой древности свойство целых чисел состо- ит в том, что еcли m, n ∈ Z, причем n > 0, то cущеcтвуют единcтвенные q, r ∈ Z такие, что m = qn + r, где 0 ≤ r < n. Число q называется непол- ным частным (quotient) при делении m на n, а число r — остатком (remainder). Операция, вычисляющая q и r по m и n называется деле- нием с остатком. Внутренние функции Quotient и Mod как раз и ищут по числам m и n их неполное частное и остаток. Заметим, что неполное частное двух целых чисел это в точности целая часть их частного, так что Quotient[m,n] всегда дает тот же результат, что Floor[m/n]. Quotient[m,n] неполное частное при делении m на n Mod[m,n] остаток от деления m на n Предостережение. По этому поводу стоит подчеркнуть, что подавля- ющее большинство русскоязычных книг по программированию аб- солютно невозможно использовать ровно потому, что переводчики не улавливают разницы между словами ratio — частное и quotient — непол- ное частное. Полная утрата смысла при переводе с одного языка на другой явление весьма обычное. Например, большинство словарей тракуют слова accuracy и precision, speed и velocity как синонимы. Между тем, эти слова не имеют между собой ничего общего: accuracy имеет размерность измеряемой величины, а precision — величина безразмерная; velocity обозначает вектор (скорость), а speed — скаляр (модуль скорости). Пере- водчики компьютерной литературы всегда характеризовались счастливым сочетанием полного незнания английского языка, полного незнания русско- го языка и полного непонимания смысла происходящего 137 . Именно отсюда возникают всякие анекдотические остаточные классы вместо правильных классов вычетов и тому подобная галиматья. 2.1. Дайте рекурсивные определения функций Quotient и Mod. Решение. Например, так q[0,m ]:=0; r[0,m ]=0; q[n ,m ]:=q[n-1,m]+If[r[n-1,m]+1==m,1,0]; q[n ,m ]:=(r[n-1,m]+1)*If[r[n-1,m]+1 2.3. Убедитесь, что m!n! делит (m + n)!. 2.4. Какой остаток дает число 2 2019 − 1 при делении на 2 20 − 1? 136 There is division betwixt the Dukes, and a worse matter than that. c William Shake- speare, King Lear 137 Впрочем, в последние годы уточнение компьютерной литературы стало излишним. 343 2.5. Какой остаток дает число 20192019 . . . 2019 (100 раз) при делении на 133? 2.6. Убедитесь, что остаток от деления простого числа на 30 равен 1 или простому числу. Какое свойство числа 30 при этом используется? По умолчанию остаток при делении m на n, возвращаемый функцией Mod, лежит между 0 и n − 1. Однако, во многих теоретико-числовых и комбинаторных алгоритмах полезно использовать деление с отступом d, когда m представляется в виде m = qn + r, где d ≤ r < d + n. Quotient[m,n,d] неполное частное при делении m на n с отступом d Mod[m,n,d] остаток от деления m на n с отступом d Таким образом, по определению Mod[m,n,d]=m-Quotient[m,n,d]*n. В ком- бинаторных алгоритмах особенно часто используется отступ 1, а в теорети- ко-числовых — отступ −n/2 (“симметричная система вычетов”). 2.7. Дайте рекурсивные определения Quotient[m,n,d] и Mod[m,n,d]. 3. Модулярная арифметика. 138 Рассмотрим некоторое натуральное число m. Говорят, что x, y cравни- мы по модулю m, и пишут x ≡ y (mod m), еcли их разноcть делитcя на m. Это означает в точности, что x и y дают одинаковые оcтатки при делении на m. Например, два числа сравнимы по модулю 2 в том и только том слу- чае, когда они оба одновременно четны или оба одновременно нечетны. Два числа сравнимы по модулю 3 в том и только том случае, когда они оба одновременно делятся на 3, оба одновременно дают остаток 1 или оба одновременно дают остаток 2 при делении на 3. Отношение cравнимоcти по модулю m предcтавляет cобой отношение эквивалентноcти на Z. Иными словами, оно обладает следующими свой- ствами. • Рефлексивность: x ≡ x (mod m). • Симметричность: x ≡ y (mod m) ⇐⇒ y ≡ x (mod m). • Транзитивность: x ≡ y (mod m) и y ≡ z (mod m) = ⇒ x ≡ z (mod m). Клаccы этой эквивалентноcти имеют вид x = x mod m = x + m Z, они cоcтоят из вcех чиcел, дающих при делении на m тот же оcтаток, что x. Эти клаccы называютcя клаccами вычетов по модулю m. 138 A mathematician called Ben Could only count modulo ten He said `When I go Past my last little toe I have to start over again.' 344 Так как оcтаток при делении любого целого числа на m > 0 может при- нимать лишь значения 0, 1, 2, . . . , m − 1, то имеетcя ровно m клаccов выче- тов по модулю m, а именно, клаccы 0, 1, 2, . . . , m − 1. Множеcтво клаccов вычетов по модулю m обозначаетcя обычно Z/mZ и называется кольцом классов вычетов по модулю m. Любое множеcтво предcтавителей этих клаccов называетcя полной cиc- темой вычетов по модулю m. Очевидным примером полной cиcтемы вы- четов по модулю m являетcя набор 0, 1, 2, . . . , m − 1, но в некоторых во- проcах удобнее брать другие cиcтемы вычетов, например, для упрощения вычислений в качеcтве cиcтемы вычетов по модулю m = 2l + 1 обычно удобнее брать −l, . . . , −1, 0, 1, . . . , l. В действительности, отношения сравнения по фиксированному модулю m является не просто отношением эквивалентности на Z, а конгруэнцией. Иными словамит, оно согласовано с основными арифметическими операци- ями. • Если x ≡ y (mod m) и z ≡ w (mod m), то x + z ≡ y + w (mod m). • Если x ≡ y (mod m) и z ≡ w (mod m), то xz ≡ yw (mod m). Эти свойства утверждают, что формулы сложения и умножения по мо- дулю m x + y = x + y, x · y = xy, служат корректными (не завиcящими от выбора предcтавителей) опреде- лениями операций на множеcтве клаccов вычетов Z/mZ. Легко проверить, что эти операции задают на Z/mZ cтруктуру коммутативного кольца c 1. Клаcc x элемента x по модулю m в том и только том cлучае обратим в Z/mZ, когда x взаимно проcт c m. Кольцо клаccов вычетов Z/mZ по мо- дулю m в том и только том cлучае являетcя полем, когда m = p — проcтое чиcло. Поcтроенное нами поле Z/pZ из p элементов обозначетcя обычно F p и называетcя полем из p элементов или проcтым полем характериcтики p. Иногда оно обозначаетcя F ( p) и называетcя полем Галуа из p элементов (при этом GF является сокращением от Galois Field: In Galois Fields full of flowers primitive elements dance for hours. Приведем для примера таблицы операций по модулям 2, 3 и 4. Иными словами, мы строим кольца Z/2Z = F 2 = {0, 1}, Z/4Z = F 3 = {0, 1, 2} и Z/4Z = {0, 1, 2, 3} из двух, трех и четырех элементов. При этом для краткости мы опускаем черту над классом и пишем просто x вместо x. + 0 1 0 0 1 1 1 0 × 0 1 0 0 0 1 0 1 + 0 1 2 0 0 1 2 1 1 2 0 2 2 0 1 × 0 1 2 0 0 0 0 1 0 1 2 2 0 2 1 345 + 0 1 2 3 0 0 1 2 3 1 1 2 3 0 2 2 3 0 1 3 3 0 1 2 × 0 1 2 3 0 0 0 0 0 1 0 1 2 3 2 0 2 0 2 3 0 3 2 1 3.1. Реализуйте операции сложения и умножения по модулю m. 3.2. Постройте таблицы сложения и умножения по модулям 5, 6 и 7. 4. Алгоритм Эвклида. 139,140 Из основной теоремы арифметики вытекает, что наибольший общий де- литель двух чисел моментально находитcя, еcли извеcтно их разложение на простые множители. Однако, практичеcкое разложение на простые множители являетcя cовершенно нетривиальной задачей. Тем бо- лее замечательно, что с глубокой древности известны быcтрые алгоритмы нахождения наибольшего общего делителя и его линейного предcтавления, не требующие разложения на простые множители! Эти алгоритмы основа- ны на наблюдении, что gcd(x, y) = gcd(x − y, y) = gcd(y, x − y). Традиционно эти алгоритмы известны под собирательным именем ал- горитма Эвклида. Версия этого алгоритма была известна в Греции при- мерно за два века до Эвклида, а его — более эффективные! — варианты с незапамятных времен использовались в древнем Египте, Китае и Индии. Алгоритм Эвклида и его модификации и сегодня остаются одним из ос- новных инструментов модулярной арифметики. Кроме того, он теснейшим образом связан со многими классическими вопросами математики, в част- ности, с непрерывными дробями. Описанный в Элементах Эвклида алгоритм по сути cоcтоит в cледу- ющем 141 . Пуcть x, y ∈ Z, заменяя x и y на их абсолютные величины и пользуясь тем, что gcd(x, y) = gcd(y, x), можно с самого начала считать, что 0 ≤ y ≤ x. Если y = 0, то gcd(x, y) = x. Если же y 6= 0, то заменяя (x, y) на (y, x − y), мы получим пару чисел с тем же наибольшим общим делителем. При этом большее из чисел y, x − y меньше, чем x. Повторяя эту процедуру, мы будем получать все меньшие и меньшие пары натураль- ных чисел. Ясно, что этот процесс должен оборваться на конечном шаге, а оборваться он может только на паре вида (d, 0). Так как наибольший общий делитель пары при этом не изменился, то gcd(x, y) = gcd(d, 0) = d. 139 The Euclidean algorithm is the granddaddy of all algoriths, because it is the oldest nontrivial algorithm that has survived to the present day. c Donald Knuth 140 Trespassers will be shot, survivors will be shot again! 141 Разумеется, Эвклид не рассматривал ни отрицательных чисел, ни нуля, да и еди- ница была числом лишь с большой натяжкой, так что его формулировки назойливо ре- петитивны и тяжеловесны, но по существу в предложениях 1 и 2 Книги VII говорится именно это. 346 4.1. Напишите программу, реализующую первоначальный алгоритм Эв- клида. Решение. Да чего там, нужно просто перечислить все использованные свойства наибольшего общего делителя, а дальше система сама решит, что делать: gcd[x ,y ]:=gcd[Abs[x],Abs[y]] /; x<0||y<0 gcd[x ,0]:=x gcd[x ,y ]:=gcd[y,x] /; x Напомним, что /; = Condition вызываемое в формате lhs:=rhs /; test задает присваивание с условием. При этом lhs полагается равным rhs только если test дает значение True. Сегодня вместо вычитания в алгоритме Эвклида обычно используется деление с остатком. А именно, если x = qy + r, то gcd(x, y) = gcd(y, r), поэтому на шагом алгоритма Эвклида может быть замена пары (x, y) на пару (y, r). Именно в таком варианте этот алгоритм обычно излагается в учебниках алгебры. 4.2. Напишите программу, реализующую версию алгоритма Эвклида, ис- пользующую деление с остатком. Уже в самом примитивном виде алгоритм Эвклида является несравнен- но более эффективным способом нахождения наибольшего делителя двух чисел, чем разложение этих чисел на множители. 4.3. Сравните время работы реализованного Вами алгоритма Эвклида на парах случайных целых чисел с несколькими десятками разрядов и время работы встроенной функции FactorInteger. Эффективность работы алгоритма Эвклида в массовом случае основана на том, что с очень большой вероятностью наибольший общий делитель двух случайных чисел очень мал. 4.4. Убедитесь, что с вероятностью > 99% наибольший общий делитель двух случайных 100-разрядных чисел меньше 1000. В действительности, знаменитая теорема Дирихле 1849 года утверждает, что с вероятностью 6/π 2 ≈ 0.607927 два случайных целых числа взаимно просты. 4.5. Проверьте утверждение этой теоремы для случайных 100-разрядных чисел. 4.6. Убедитесь, что для любого натурального n существуют натуральные числа x и y такие, что в алгоритме Эвклида требуется ровно n делений. 4.7. Убедитесь, что наименьшие натуральные числа, для которых в алго- ритме Эвклида требуется ровно n делений, это числа Фибоначчи x = F n+2 , y = F n+1 Однако, алгоритм Эвклида далеко не оптимален и его легко улучшить. Во-первых, алгоритм сходится несколько быстрее, если на каждом шаге 347 брать в нем не неотрицательный, а наименьший по модулю остаток — вот где понадобится деление с отступом! 4.8. Напишите программу, реализующую алгоритм Эвклида с выбором на каждом шаге наименьшего по модулю остатка. Указание. Как и в предыдущей задаче используйте функцию Mod, но теперь не от двух, а от трех аргументов. Еще более существенная экономия получается, если применять деление с остатком только к нечетным числам, а для четных чисел использовать деление пополам. А именно, • если оба числа x, y четны, то gcd(x, y) = 2 gcd(x/2, y/2); • если четно ровно одно из них, скажем y, то gcd(x, y) = gcd(x, y/2). Таким образом, вычисление наибольшего общего делителя двух целых чи- сел сводится к делению пополам и вычислению наибольшего общего дели- теля двух нечетных чисел. В классическом китайском труде Математика в девяти книгах содержится алгоритм вычисления gcd(x, y), основанный на этой идее. Разумеется, фактически и там не производилось никакого деления с остатком, а меньшее из чисел x или y просто вычиталось из большего. В отличие от классического алгоритма Эвклида в данном слу- чае вычитание может быть даже лучше, чем деление с остатком, так как разность двух нечетных чисел четна и, значит, алгоритм сходится очень быстро. Этот алгоритм называется бинарным алгоритмом. 4.9. Напишите программу, реализующую классический китайский бинар- ный алгоритм. То же для варианта бинарного алгоритма, использующего деление с остатком вместо вычитания. В учебниках высшей алгебры обычно говорится, что проделав обратный ход в алгоритме Эвклида можно найти линейное представление d = ax+bx наибольшего общего делителя d = gcd(x, y) чисел x и y. Однако, класси- чески известно, что совсем небольшая модификация алгоритма Эвклида позволяет искать наибольший общий делитель d одновременно с его ли- нейным представлением. Эта модификация, известная как расширенный алгоритм Эвклида = extended Euclid algorithm 142 , была развита ин- дийскими математиками V–VI века в связи с китайской теоремой об остат- ках и в явном виде описана Бхаскара I. Единственное изменение, которое при этом необходимо внести в обычный алгоритм Эвклида, состоит в том, что вместо целых чисел рассматриваются строки длины 3 с целыми компо- нентами, последняя из которых отвечает исходному числу, а первые две — коэффициентам его представления как линейной комбинации x и y. Таким образом, алгоритм начинается со строк (1, 0, x) и (0, 1, y). Шаг алгоритма состоит в том, что строки (u, v, x) и (w, z, y) заменяются на • строки (w, z, y) и (u − w, v − z, x − y) в варианте, использующем вычи- тание; 142 Откуда ExtendedGCD. Иногда, в том числе и в русском переводе книги Кнута, оши- бочно называется обобщенным алгоритмом Эвклида. 348 • строки (w, z, y) и (u − qw, v − qz, r), где x = qy + r, в варианте, исполь- зующем деление с остатком. Так как при этом третья координата ведет себя так же, как остатки в обыч- ном алгоритме Эвклида, то через конечное число шагов мы неминуемо при- дем к строкам вида (a, b, d) и (u, v, 0), в этот момент алгоритм останавли- вается и мы можем заключить, что d = gcd(x, y) и d = ax + by. 4.10. Напишите программы, реализующие расширенный алгоритм Эвкли- да в обоих вариантах. Отметим две замечательные особенности этого алгоритма. Во-первых, он является самопроверяющимся, так как наибольший делитель, это в точ- ности общий делитель, допускающий линейное представление. Во-вторых, он дает полезный субпродукт (= by-product). А именно, тот факт, что вто- рая строка, получающаяся на момент остановки алгоритма, равна (u, v, 0), означает, что ux + vy = 0. 4.11. Что можно сказать об u и v, получающихся на момент остановки расширенного алгоритма Эвклида? Указание. Проведите эксперимент! Все описанные выше алгоритмы моментально обобщаются на случай лю- бого количества чисел. Конечно, можно воспользоваться ассоциативностью операции gcd и искать наиброльший общий делитель нескольких чисел по индукции, например, для трех чисел так gcd(x, y, z) = gcd(gcd(x, y), z). 4.12. Реализуйте рекурсивный алгоритм для вычисления наибольшего об- щего делителя нескольких чисел и его линейного представления. Для небольших примеров рекурсивный алгоритм будет работать, но лег- ко предложить гораздо более эффективные алгоритмы! 4.13. Реализуйте несколько различных вариантов алгоритма Эвклида для нескольких чисел и сравните скорость их работы с рекурсивным алгорит- мом. 4.14. Реализуйте расширенный алгоритма Эвклида для нескольких чисел. Указание. Для s чисел этот алгоритм оперирует с s целочисленными строками длины s + 1, но имеются различные варианты организации шага алгоритма. К счастью, для всех практических целей эти потуги ускорить работу ал- горитма Эвклида излишни, так как мы можем с успехом использовать внут- ренние функции GCD и ExtendedGCD. Имплементация этих функций вклю- чает не только эффективную комбинацию алгоритма Эвклида и бинарного алгоритма, но и быстрые алгоритмы точной арифметики, развитые в по- следние 15–20 лет. 5. Китайская теорема об остатках. 143 143 Я не слыхал рассказов Оссиана, Не пробовал старинного вина c Осип Мандельштам 349 Cейчаc мы установим фундаментальный результат, который позволяет • cводить изучение cравнений к примарному cлучаю, • сводить вычисления по большому модулю к вычислениям по несколь- ким маленьким модулям. Этот результат является основным инструментом при проведении быстрых вычислений с очень большими числами. Для случая произвольного количества взаимно простых модулей этот результат был извеcтен Cунь Цзу в первом веке нашей эры и иcпользовалcя для логистических и аcтрономичеcких вычиcлений. Для случая двух моду- лей излагаемый ниже алгоритм в явном виде содержится в трактате Ари- абхаты 499 года. В 1247 году Чин Чжу-Шао обобщил теорему на случай произвольного количества не обязательно взаимно простых модулей. Начнем с ключевого случая двух взаимно простых модулей, который позволяет провести индукцию. Пусть m ⊥ n — два взаимно простых моду- ля. Тогда китайская теорема об остатках утверждает, что для любых a, b существует такое x, что x ≡ a (mod m) x ≡ b (mod n) причем это x единственно по модулю mn. Иными словами, если дополни- тельно предполагать, что 0 ≤ x < mn, то x единственно. Начнем с простого но важного замечания, что x ≡ y (mod m) и x ≡ y (mod n) = ⇒ x ≡ y (mod mn). В самом деле, x − y делится как на m так и на n, а, значит, делится на lcm(m, n). Но m и n взаимно просты, так что lcm(m, n) = mn. Тем самым, единственность x очевидна и существование следует теперь из принципа Дирихле! Это значит, что если мы просто переберем все числа от 0, до mn − 1, то мы обязательно наткнемся на решение этой системы. 5.1. Реализуйте полный перебор, находящий x в китайской теореме для случая двух модулей. Впрочем, описанный метод решения трудно назвать эффективным ал- горитмом. Хотелось бы явно предъявить какое-то решение этой системы. Так как m ⊥ n, то найдутся такие c и d, что cm + dn = 1. Их можно найти, например, при помощи расширенного алгоритма Эвклида. Теперь в качестве x можно взять x = dna + cmb. В самом деле, x ≡ dna + cma ≡ a (mod m), x ≡ dnb + cmb ≡ b (mod n). Однако, указанное решение может быть ≥ mn. Чтобы получить решение, удовлетворяющее неравенствам 0 ≤ x < mn, нужно еще взять остаток dna + cmb по модулю mn. 350 5.2. Реализуйте алгоритм, вычисляющий x в китайской теореме для слу- чая двух модулей. В действительности, такой алгоритм реализован в пакете NumberTheory`NumberTheoryFunctions` под именем ChineseRemainder. Для случая двух модулей эта функция вы- зывается в формате ChineseRemainder[ {a,b},{m,n}]. С математической точки зрения эта теорема утверждает, что Z/mnZ ∼ = Z/mZ ⊕ Z/nZ, иными словами, вычисления по модулю mn полностью сводятся к вычислениям отдельно по модулю m и по модулю n. Китайcкая теорема об остатках непосредственно обобщается на случай любого количества модулей. А именно, пуcть m = m 1 . . . m s , где m i по- парно взаимно проcты, а x 1 , . . . , x s — произвольные целые чиcла. Тогда cущеcтвует такое x, что x ≡ x 1 (mod m 1 ) . . . x ≡ x s (mod m s ) причем это x единcтвенно по модулю m. Иными словами, утверждается, что если m i попарно взаимно проcты, то имеетcя изоморфизм колец Z/m 1 . . . m s Z ∼ = Z/m 1 Z ⊕ . . . ⊕ Z/m s Z, так что вычисления по модулю m = m 1 . . . m s полностью сводятся к вычис- лениям отдельно по модулю каждого из m i Проще всего доказать китайскую теорему по индукции. Она же, есте- ственно, дает и алгоритм для нахождения x. А именно, предположим, что мы уже умеем решать аналогичную систему для s − 1 взаимно про- стого модуля. Пусть y удовлетворяет первым s − 1 сравнению по модулям m 1 , . . . , m s −1 . Тогда x можно искать как решение системы x ≡ y (mod m 1 . . . m s −1 ) x ≡ x s (mod m s ) 5.3. Реализуйте рекурсивный алгоритм, находящий x в китайской теореме для любого количества модулей. Впрочем, можно не использовать индукции, а сразу указать решение. Для этого положим n i = m 1 . . . b m i . . . m s , и заметим, что числа n i взаимно просты в совокупности. Тем самым, существуют a i такие, что a 1 n 1 + . . . + a s n s = 1, их можно найти, например, при помощи обобщенного алгоритма Эвклида. Остается положить x = a 1 n 1 x 1 + . . . + a s n s x s , и, если мы хотим получить каноническое решение, поделить это x с остат- ком на m 1 . . . m s 351 5.4. Реализуйте алгоритм, непосредственно вычисляющий x в китайской теореме для любого количества модулей. После подгрузки упомятнутого выше пакета x можно искать вызывая функцию ChineseRemainder в формате ChineseRemainder[ {x1,...,xs},{m1,...,ms}]. 5.5. Пусть x s ≡ i (mod p i ) для первых s простых p i , причем 0 ≤ x < p 1 . . . p s . Верно ли, что при любом s ≥ 2 это x s |