Объясните свой ответ. 33.4-4*

Пусть /(ж) = /о + f\x + • • • + ftxt (mod р) - многочлен степени t с коэффициентами /г- £ Zp (где р - простое число). Назовём а £ Ъ,р нулём (zero) многочлена /, если f(a) = 0 (mod р). Докажите, что если а - нуль многочлена /, то найдётся многочлен д(х) степени t - 1, для которого /(ж) = (ж - а)д(х) (mod р). Выведите отсюда, что многочлен степени t имеет не более t нулей (в Ъ,р).

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

Около 100 г. до Р.Х. китайский математик Сун Цу (Sun-Tsu) решил такую задачу: найти число, дающее при делении на 3, 5 и 7 остатки 2, 3 и 2 соответственно (общий вид решения - 23 + 105/г при целых к). Поэтому утверждение об эквивалентности системы сравнений по взаимно простым модулям и сравнения по модулю произведений называют «китайской теоремой об остатках».

Пусть некоторое число п представлено в виде произведения попарно взаимно простых чисел riin2 ... пк. Китайская теорема об остатках утверждает, что кольцо вычетов Ъп устроено как произведение колец вычетов Zrai X Z„2 X • • • X ЪПк (с покомпонентным сложением и умножением). Это соответствие полезно и с алгоритмической точки зрения, так как бывает проще выполнить операции во всех множествах Zraj, чем непосредственно в Ъп.

Теорема 33.27 (Китайская теорема об остатках)

Пусть п = п\П2 пь, где щ, ,пь попарно взаимно просты. Рассмотрим соответствие

а <н> (аь а2,... , ак),(33.25)

где а £ Ъп, а{ £ ЪПг и аг- = а mod п, при г = 1,2,...,к. Формула (33.25) определяет взаимно однозначное соответствие между Ъп и декартовым произведением Zrai X Z„2 X • • • X ЪПк. При этом операциям сложения, вычитания и умножения в Ъп соответствуют покомпонентные операции над /г-элементными кортежами: если

а (а1,а2,... ,ак)

и

Ь (h, b2, , bk),

то

(a-\-b) mod n -H- ((ai+bi) mod щ, (a2-\-b2) mod n2, (a-b) mod n -H- ((ai - bi) mod щ, (a2 - b2) mod n2,

•• • , (an+bn) mod nk (33.26)

•• • , (an-bn) mod nk

(33.27)

(ab) mod га -и- ((ai&i) mod щ, (а2Ь2) mod п2, , (anbn) mod пк).

(33.28)

Доказательство

Заметим прежде всего, что формула (33.25) действительно задаёт корректно определённое отображение Ъп в указанное произведение: если два числа сравнимы по модулю га, то их разность кратна га, и потому эти числа дают одинаковые остатки при делении на любое из гц (так как гц га).

Обратное отображение также легко описать. Положим ггц = п/щ, где г = 1, 2,... , к, то есть ггц = п\п2 ...... nk. Оче-

видно, ггц = 0 (mod rij) при гф j. Положим

d = ггц(т~1 mod щ)(33.29)

при г = 1,2,... , к. Тогда сг- = 1 (mod га)г- и сг- = 0 (mod n)j при j ф г, и числу сг- соответствует набор с одной единицей на г-м месте:

с,- (0,0,... ,0,1,0,... ,0).

Тем самым, положив

а = (a\Ci + а2С2 + .. .afccfc) (mod га).(33.30)

мы получим число, соответствующее набору (а\, а2, , ак). Тем самым для каждого набора можно найти соответствующий элемент Ъп. Осталось убедиться, что такой элемент только один. Можно сослаться на то, что и слева, и справа у нас имеются множества из га = raira2 .. .nk элементов, и потому всякая сюръекция является биекцией. А можно заметить, что если а и а дают одинаковые остатки при делении на все щ, то а - а делится на все щ и в силу взаимной простоты на их произведение, то есть на га (это легко следует из однозначности разложения на множители). Следствие 33.28

Если щ, п2,... ,пк попарно взаимно просты и га = raira2 • • -га, то система сравнений

х = aj (mod гц)

относительно х (где г = 1,2,... , Аг) имеет единственное решение по модулю га.

Следствие 33.29

Если щ, п2,... ,пк попарно взаимно просты, га = raira2 • • • пк, а х на - целые числа, то свойство

х = a (mod га)

равносильно выполнению сравнений

х = a (mod гц)

Рис. 33.3 33.3 Китайская теорема об остатка: п\ = 5, п2 = 13. В столбцах перечислены различные остатки при делении на 13, в строках - при делении на 5. Каждое число от 0 до 65 - 1 помещено в соответствующую строку и столбец, и теорема гарантирует, что в каждой клетке таблицы будет по одному числу.

при всех г = 1, 2,... , к.

В качестве примера рассмотрим систему сравнений

а = 2 (mod 5), а = 3 (mod 13).

Здесь а\ = 2, аз = 3, п\ = т2 = 5, п2 = т\ = 13, и следовательно, п = 65. Поскольку 13-1 = 2 (mod 5) и 5-1 = 8 (mod 13), мы находим

ci = 13(2 mod 5) 26, с2 = 5(8 mod 13) 40,

и

а = 2-26 + 3-40 (mod 65) =52+ 120 (mod 65)

=42 (mod 65).

См. также рис. 33.3.

Таким образом, вычисления по модулю произведения взаимно простых чисел можно выполнять отдельно по модулю каждого из этих чисел.

Упражнения

33.5-1

Найдите все ж, при которых ж = 4 (mod 5) и ж = 5 (mod 11). 33.5-2

Найдите все целые числа ж, дающие при делении на 2, 3, 4, 5, 6 остатки 1, 2, 3, 4, 5 (соответственно). 33.5-3

Докажите, что (в контексте теоремы 33.27) при gcd(a,ra) = 1 имеет место соответствие

(a-1 mod п) -и- ({а1 mod rai), (a2l mod n2),... , (a1 mod пк)).

33.5-4

Пусть /(ж) - многочлен с целыми коэффициентами. Докажите, что (в условиях теоремы 33.27) число его корней по модулю п (вычетов, для которых /(ж) = 0 (mod п)) равно произведению чисел его корней по модулям щ, п2,... ,пк.