Прямые уравнения

где /П; взаимно просты

Обратные уравнения к

с = 2; c,H,Mi (mod М)

где Л1 = ri т,- Mi = Mlmi

и Л; являются решсниями уравнений AiMj -Ь пт - 1

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

существует взаимно однозначное соответствие. Предположим, что с = 2, q = 1 и = 2. Тогда эти условия приводят к следующим возможностям:

се 12, 5, 8, 11, И, 17, 20, 23, 26, 29, ...},

с € 1, 5, 9, 13, 17, 21, 25, 29, 33, ...[,

с £ {2, 7, 12, 17, 22, 27, 32, 37, ...,

Единственным решением служит с = 17. Позже будет дан простой алгоритм вычисления числа с по его вычетам.

В рассмотренном примере число однозначно было восстановлено по его вычетам. В следующей теореме доказывается, что это имеет место в общем случае.

Теорема 2.8.1. Для заданного множества целых положительных попарно взаимно простых чисел Шд, т и множества неотрицательных целых чисел Сд, с, с при Ci < /п; система

Ct = с (mod ш;), i = О, .... к,

имеет не более одного решения в интервале 0-<;c<JXmj.

Доказательство. Предположим, что с и с являются двумя лежащими в рассматриваемом интервале решениями. Тогда

с = Qimt -f~c, и с = Qlmi + ci и, следовательно, с - с кратно т, для каждого I, а так как mj попарно взаимно просты, то с - ck кратно Y1 i- Но число с - г

лежит между - Цт, - ij и П :- Единственным положитель-

ным числом, удовлетворяющим этим условиям, является с - С = = 0. Следовательно, с = с. □

Имеется простой путь построения решения системы сравнений из теоремы 2.8.1, основанный на следствии из алгоритма Евклида. Согласно этому следствию, в кольце целых чисел для каждого s и t найдутся такие о и д, что

НОД Is, Л es + bt.

Для заданного множества попарно взаимно простых положительных чисел /По, mi, т, используемых в качестве модулей,

положим М = IT ! ~ Mjmi. Тогда НОД [Mi, ml - 1,

и, следовательно, существуют такие целые Л,- и л;, что

iVjMi + л,тг = 1, ( = О,

Теперь можно доказать следующую теорему.

Теорема 2.8.2. Пусть М = Цл!; - произведение попарно вза-

имно npocmbtx положительных чисел, пусть Mi = Ж/т и пусть для каждого i Ni удовлетворяют равенствам iVjAI, + (Ш; = 1. Тогда единственным решением системы сроинений

Ci = с (mod mi), i = О..... к.

с = Е CiNiM, (mod М).

Доказательство. Поскольку мы уже знаем, что решение рассматриваемой системы сравнений единственно, надо только доказать, что выписанное выше с действительно является решением. Но для такого с

С = S c,N,M, = CiNiMi (mod m,),

ибо т, делит Mr при г Ф i. Наконец, так как NiMj + njmi = 1, то /viMi = 1 (mod Ш() и с = (mod т,), что и завершает доказательство. □

Чтобы проиллюстрировать теорему 2.8.2, продолжим предыдущий пример. Заметим, что М = 60, М = 20, Mi = 15 и Afj = 12. Далее, как можно вычислить по алгоритму Евклида или просто проверить, 1 = (-1) .М + 7т , 1 = (-1) Mi + imi,

Прямые уравнения

£<> (х)= RiOjj tWl. = О.....*

где т (х) взаимно просты

Обратные уравнения k

с{х)= Е W iV МЛ > W (mod ММ)

где М(х}= и т W, М (х) = М (i)/m< (х)

и Л* (х) являются решениями уравнений (х) Л1<> (jt) + л > W т > (х) = 1

Рис. 2.3. Китайская теорема об остатках для многочленов.

1 = (~2) Alj + Smj. Следовательно, Ni,M = -20, iViMj = -15, iVjAlj = -24 и

с = -20с - 15с, - 24cj (mod 60).

В частности, при Cj = 2, с, = 1 и с, = 2 имеем с = -103 (mod 60) = 17, что мы видели и раньше.

Китайская террема об остатках является основой представления целых чисел, в котором просто выполняется операция умножения. Допустим, что надо выполнить умножение с = ab. Пусть at = Rmi la], bi = R i [b] и с, = Л , Icl для каждого i = = О, k. Тогда Ci = uibi (mod itit), и это умножение вычислить легче, так как и bi являются малыми целыми числами. Аналогично, при сложении с = а + b имеем Ci = а, + bi (mod rrii) для всех ! = О, k. В обоих случаях для получения окончательного ответа с должно быть восстановлено по вычетам в соответствии с китайской теоремой об остатках.

Переход к системе вычетов позволяет разбить большие целые числа на маленькие кусочки, которые легко складывать, вычитать и умножать. Если вычисления состоят только из этих операций, то такое представление является альтернативной арифметической системой. Если вычисления достаточно просты, то переход от естественной записи целых чисел к записи через систему остатков и обратное восстановление ответа в целочисленном виде могут свести на нет все возможные преимущества при вычислениях. Если, однако, объем вычислений достаточно велик, то такой переход может оказаться выгодным. Это происходит потому, что при вычислениях все промежуточные результаты можно сохранять в виде системы остатков, выполняя обратный переход к целочисленному виду только при окончательном ответе.

В кольце многочленов над некоторым полем также имеется китайская теорема об остатках, формулировка которой приведена на рис. 2.3 и которая доказывается по той же схеме, что и для целых чисел.

Теорема 2.8.3. Для заданкого множества попарно взаимно простых многочленов (). яИ (х)..... т<) (х) и множества многочленов с< > (*). oW (х), с (х), таких что deg с (х) < < deg m > (х) система ураенений

с( (X) = с (х) (mod mti (х)), i = О.....k,

имеетне более одного решения с{х), удовлетворяющего условию

deg с (х) < Е deg m ) (х).

Доказательство. По существу доказательство совпадает с доказательством теоремы 2.8.1. Предположим, что имеются два решения, а именно

c(x) = QW(x)m<-Hx) + cW(x)

с(x) = Qm(x)mW(x) + cm(x),

так что разность с (х) - с (х) кратна многочлену mi> (х) для каждого !. Тогда многочлен с (х) - с (х) кратен и многочлену

П т (л:), причем

< [с (х) - с (X)] < deg П т<

Следовательно, с (х) - с (х) = О, и доказательство закончено. □ Система сравнений может быть решена так же, как и в случае кольца целых чисел. В кольце многочленов над некоторым полем для любых заданных s (х) и t (х) существуют многочлены а (х) и b (х) удовлетворяющие условию

НОД [S (х), ((х) \) = а (х) S (х) + 6 (х) t (х). k

Пусть М (х) = Ylm) (х) и М (х) = М (x)lmi (х); тогда

НОД [М1> (х), т<> (х)1 = 1. Пусть iV<> (х) и п (х) удовлетворяют равенству

JVC! (х) MW (х) + п<> (х) т<1 (х) = 1.

Теорема 2.8.4. Пусть М (х) = П М ~ произведение по-

парно взаимно простых многочленов; пусть (х) = М {х)/т > (х) и для всех i многочлены (х) удовлетворяют условиям

Л) (х) Ж(0 (х) + пО {У) т() (х) = 1. Система сравнений

с() (х) = с {х} (mod m() (л:)), i = О.....k,

имеет единственное решение, даваемое многочленом

с (х) = Д с() Л() (д:) M(i (х) (mod Л1 (а:)).

Доказательство. Нам нужно только доказать, что многочлен с (х) удовлетворяет каждому сравнению данной системы. Но с {х) = c<f (х) ЛГ(0 (х) Л1(0 (х) (mod mt> (х)),

так как т(> (х) является делителем многочлена Л1< (х), если г # i. Наконец, так как Л* (х) М (х) + n (х) т(> (х) = 1 то iV< (х) уИ() (х) = I (mod /к<) (х)) и с (х) - (x)(mod (х)), что и завершает доказательство теоремы. С

Задачи

2.1. а. Показать, что существует только одна группа с тремя элементами. Построить ее и показать, что она абелева.

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

2.2. Пусть групповая операция на группах из задачи 2.1 называется сложением.

а. Определить умножение на трехэлементной группе так, чтобы она стала кольцом. Является ли такое определение единственным?

б. Для каждой из четырехэлементных групп определить умножение так, чтобы превратить нх в кольца. Является лп каждое определение единственным?

2.3. Какое из трех построенных в задаче 2.2 колец является полем? Можно ли задать другое умножение так, чтобы получить поле?

2.4. Доказать, что в пмклическон группе с q элементами выполняются равенства а-? (j-l

2.6. а. Показать, что 7 X Zg изоморфно Zg.

6. Показать, что X Z4 не изоморфно Zg.

2.6. Привести пример кольца без единицы.

2.7. Отталкиваясь от пары {V} преобразования Фурье, доказать следующие стандартные свойства дискретного преобразования Фурье:

а. Линейность: {av. + bv.j -м- jaV +

б. Свойство сдвига: tj- jjj -> {о) Vf\.

в. Модуляционное свойство; (tt,-[ jj .

2.8. Показать, что преобразование Фурье вектора данных vi = о/ где г - целое число, содержит единственную ненулевую спектральную компоненту. Какова эта компонента, если г = О? Показать, что все спектральные компоненты вектора, имеющего только одну ненулевую компоненту, не вавны нулю.

2.9. Доказать, что если А - теплицева матрица, а J - обменная матрица той же размерности, то = JAJ.

2.10. а. Найти НОД 11573,308], используя алгоритм Евклида.

б. Найти целые чнсла А и В, удовлетворяющие равенству НОД 11573,3081 - .1573 +В-308. 2.11. Рассмотрим множество S =\{0, 1, 2, 3}, на котором заданы операции

Является ли это множество полем? 2.12. Доказать, что комплекснозначное дискретное преобразование Фурье удовлетворяет условию симметрии

k = d.....п -I.

тогда и только тогда, когда преобразуемая последовательность данных является вещественной.

2.13. Пусть G - произвольная группа (не обязательно конечная). Условимся называть групповую операцию умножением и единичный элемент единицей. Пусть g - произвольный элемент группы и v - наименьшее положительное число, если оно существует, такое что g = 1, где под g понимается у-кратное произведение g * g * * g- Доказать, что подмножество (g. g 8 - ё\ образует в G подгруппу. Доказать, что эта подгруппа является абелевой даже тогда, когда G неабелева группа.

2.14. Доказать, что множество вещественных чисел вида {а+&К2, где а I) Ь - рациональные числа, образует поле относительно обычных операций сложения и умножения.

2.15. Кольцо кватернионов состоит нз всех выражений вида

о о 4- Qii Н- Да/ Н- ask,

где 1Ц, Qi, Яд и йа - вещественные числа, а /, / и ft - неопределенные переменные. Сложение и умножение определяются правилами

а+ 6- 6о)+ (аг+ + (03+2)/+ ) г.

аЬ - [Qobf, - a-ipi - аЬ - аф -1-

+ (ОаЬо Ч- аф + афч - афз) / +

+ (афо - аф + афз + афз) к.

Доказать, что кольцо кватернионов действительно образует кольцо, но не поле. Какое из свойств поля в этом кольце не выполняется?

2.16. Доказать теорему 2.2.5.

2.17. Поле из трех элементов GF (3) задано арифметическими таблицами