Глухов М. М. Алгебра том 1 (1016678), страница 18
Текст из файла (страница 18)
~ 3. Решение сравнений Рассмотрим вопрос о решении в кольце Ж/т простейшего уравнения: ~а] (х] = (Ь] Из (2) и определения 3 следует, что задача описания всех решений этого уравнения в кольце Ж/т эквивалентна задаче описания всех решений сравнения: ах = т(шорт) (5) в целых числах относительно неизвестного х.
Рассмотрим более общее сравнение по модулю т с неизвестным х: авх" + а|х" 1+... + а„|х + а„= — 0(шорт). (6) (7) тУ+ а~ = 1. Отсюда следует, что а~ = 1(тосе т), и потому а(УЬ) = Ь(шорт). Значит, число УЬ удовлетворяет сравнению (5), и сравнение (5) разрешимо. Допустим, что х1, х2 — два решения сравнения (5).
Тогда имеем ах1 =— ах2(шорт), и в силу теоремы 2 г) х1 = — х2~шос1т). О п р е д е л е н и е 5. Решением сравнения (6) называется любое целое число хв, при подстановке которого вместо х сравнение (6) становится верным числовым сравнением. О п р е д е л е н и е 6. Два сравнения (по одному или по разным модулям) называются равносильны ки, если множества их решений совпадают. Прежде чем решать сравнение (5), сделаем два общих замечания, следующих непосредственно из теоремы 2. 3 а м е ч а н и е 2.
Если в сравнении (6) любой из коэффициентов а, заменить сравнимым с ним по модулю числом, то получится сравнение, равносильное исходному. Следовательно, сравнение (6) всегда можно привести к сравнению с коэффициентами из множества О, т — 1. 3 а м е ч а н и е 3. Если целое число хв является решением сравнения (6), то его решениями являются все числа класса ~хо],„. Все эти решения называют одинаковыми по модулю т. Решения же, не сравнимые по модулю т, называют различными по модулю т. Следовательно, для нахождения всех решений сравнения достаточно найти по одному представителю из каждого класса чисел по модулю т, удовлетворяющих данному сравнению.
Число этих представителей называют числом решений 7зо модулю т. Вернемся к вопросу о решении сравнения (5). Исчерпывающий ответ на него дают две нижеследующие теоремы. Т ео р ем а7. Если (а, т) = 1, то сравнение(5) имеетп единственное решение 7зо модулю т. П Так как (а, т) = 1, то существуют такие У, У Е Ж, что 4. Заказ И 573. 97 96 (9) а/с1 х = Ь/И(пюс1т/И). 2775х = 825(пюс1 264).
(хв]т, = (х+т19: я Е,'Ц. (12) 279х = 201(пюс1 264), Покажем, что числа; д1 = 2, дг = 4, дз = 4, д4 = 2. 93х = 67(пюс1 208). (13) 98 99 Следовательно, сравнение (5) имеет единственное по модулю т решение 1'Ь: х = Щпюс1т). П (8) Т е о р е м а 8. Если (а, т) = И, то сравнение (5) разрешимо в том и только там случае, когда И ] Ь. При выполнении последнего условия сравнение (5) имеет равно И решений по модулю т. П Если сравнению удовлетворяет некоторое число хо, то по теореме 4 т ] а — Ь, и потому И ] а — Ь.
Отсюда и из условия И ] а следует, что й ] Ь. Пусть теперь выполнено условие И ] Ь. Тогда по теореме 2 сравнение (5) равносильно сравнению: Так как (а/И, т/И) = 1, то по теореме 7 сравнение (9) имеет единственное по модулю т/й решение хо. Остается выяснить, сколько различных по модулю т чисел содержится в классе чисел (хо],„„где т1 = = т/И. По определению классов вычетов: хо,хо+ т1,хо+ 2т1,...,хо+ (И вЂ” 1)т1 (10) попарно не сравнимы по модулю т и любое другое число из (хо] сравнимо с одним из чисел ряда (10). Действительно, если хо + гт1 = = хв + ут1(пюс1 т), где 0 < г < ~ < й — 1, то т ] (у — г)т1, что невоз- можно, поскольку О < (у — ~)т1 < Ит1 = т.
Пусть теперь хо + т1о— любое число из класса (хо],. Разделив о на й с остатком, получим: д = й~1+ т, О < т < й — 1, хв + т1о = хв + т|йу1 + гт1 = хв + тт1 + о1т = хо + тт1(тосе т). Таким образом, сравнение (5) в рассматриваемом случае имеет ровно И решений по модулю т: хь = хв + /ст1(пюс1 т), /с = О, 1,..., И вЂ” 1. П Из доказательства теоремы 8 видно, что нахождение решений сравнения ~5) сводится к случаю, когда (а, т) = 1.
В этом случае решение сравнения (5) при небольших т можно найти перебором и непосредственной проверкой представителей из классов кольца (например, чисел 0,1,...,т — 1). В общем случае можно воспользоваться методом, указанным при доказательстве теоремы 7. С этой целью необходимо найти сначала целые числа У, У, удовлетворяющие равенству (7), после чего решение находится по формуле (8).
При этом для нахождения числа У можно воспользоваться алгоритмом, указанным в ~ 2.1Ч. Напомним, что для этого нужно найти последовательность неполных частных о1, о2,..., о„в алгоритме Евклида, примененном к числам т, а, а затем, положив ~~ = 1, У1 = — о1, найти по рекуррентной формуле ~~, = ~~, 2 — У~, 1щ последовательность чисел ~~,..., ~„. Последнее число Р„равно искомому ~.
П р и м е р 2. Решить сравнение: Заменив коэффициенты этого сравнения остатками от деления их на модуль 624, получим сравнение: равносильное сравнению (11). Применяя к числам 624, 278 алгоритм Евклида, получим их НОД 3 и систему неполных частных: Так как 201 делится на 3, то сравнение (12) разрешимо, имеет ровно 3 решения по модулю 624 и эквивалентно сравнению: Для решения этого сравнения нам нужна последовательность частных в алгоритме Евклида для чисел 208, 93. Однако легко видеть, что она бу- дет той же, что и для чисел 624, 279. Для нахождения чисел ~~,..., ~4 = = ~ удобно воспользоваться таблицей 4.1Ч.
Теперь по формуле (8) находим решение сравнения (13) по модулю 208: ж = 79(шос$208). Отсюда, пользуясь теоремой 8, найдем все три решения сравнения (11) по модулю 624: ж1 = 79 ~2 = 79+ 208 = 287 ~з = 79+ 208 2 = 495. ж = а1(шод т1), ж = а2(шод т2), ..., ж = ак(пюй т~) (14) имеет единственное решение по модулю т = т1т2... т~ при любью а1,а2, .,а~ Е Ж.
П Докажем теорему индукцией по й. При й = 1 ее утверждение верно согласно теореме 7. Пусть й > 1. По предположению индукции система, составленная из первых й — 1 сравнений системы (14), имеет единственное решение по модулю т' = т1т2... т~ 1 . ж = а(шод т'). Так как класс [а) совпадает с множеством всех чисел вида: (15) к=а+ту, где у — любое целое число, то для нахождения всех решений системы (14) остается найти те значения у, при которых числа вида (15) удовле- творяют последнему сравнению системы (14). С этой целью заменим в нем ж на а+ т'у и решим полученное сравнение: т'у = а~ — а(пюд т~) относительно у. Так как (т', т~) = 1, то по теореме 7 оно имеет единственное решение по модулю т~. Пусть это будет класс [6) „, т.
е. множество чисел (б+ т~$: 8 Е Ж). Отсюда и из (15) имеем: множество решений системы (14) совпадает с множеством чисел вида а+ бт'+ т~, т. е. с классом [а+ бт'] . П Заметим, что из доказательства теоремы 9 виден и алгоритм решения системы (14): 1) из первого сравнения находим ж = а1+ т1у; Рассмотрим еще вопрос о решении простейшей системы сравнений. Т е о р е м а 9 (китайская теорема об остатках). Если натуральньсе числа т1, т2,..., т~ попарно взаимно просты, то система сравнений: 2) подставив во второе сравнение а1+ т1у вместо ж и решив полученное сравнение относительно у, получим, у = 61+ т28, и потому х = а1 + т161 + т1т28' 3) подставляем найденные значения ж в третье сравнение системы и находим Ф, и т. д. Задачи 1.
Пусть р1, р2 — отношения сравнимости целых чисел по модулям т1, та соответственно. Выяснить, являются ли отношениями сравнимости по подходящим модулям отношения р1 П р2, р1 0 р2, р1 р2. В каком случае имеет место включение р1 С р2? 2. Показать, что все натуральные числа любого класса вычетов [а) образуют бесконечную арифметическую прогрессию. Найти ее первый член и разность. Сколько чисел, попарно не сравнимых по модулю т1, содержится в [а) для любого т1 е Ж? 3. Элемент а любого кольца В называется нильпотентным, если существует такое и Е 1Ч, что а" = О. Описать все нильпотентные элементы кольца Ж/т и выписать формулу для нахождения числа таких элементов.
При каком условии все необратимые элементы кольцам Ж/т являются нильпотентными? 4. Найти условия, при которых все элементы группы (Ж/т;+) являются кратными одного ее элемента [а) . Сколько таких элементов существует в группе (Ж/т;+)? 5. Найти наименьшее натуральное число й, удовлетворяющее равенству Й[а) = [О), а также число классов [а) е Ж/т, удовлетворяющих указанному равенству при данном значении Й. 6. Выписать группы обратимых элементов колец Ж/16 и У/24.
Существуют ли в них элементы, степенями которых являются все элементы соответствующих групп? Изоморфны ли эти группы? 7. Выписать все подкольца кольца Ж/18. Какие из них изоморфны кольцам вычетов по другим модулям? 8. В кольце Ж/975 найти элементы, обратные к элементам [13)975, [223) 975.
9. Доказать, что любое простое число делит число (р — 1)! + 1. (Это утверждение называют в теории чисел теоремой Вильсона в честь английского математика Д. Вильсона (1741 — 1793).) 100 101 Глава У1 КОЛЬЦА МАТРИЦ ~ 1. Матрицы над кольцом и операции над ними Матрицы размеров и х и называют квадратными матрицами порядка и. Матрицы размеров 1 х и и и х 1 называют соответственно вектор-строками и вектор-столбцами. Квадратные матрицы: 0 0 . асс а„д айаг адд адг ... ад„ 0 ада ...
ад„ адд 0 ... 0 агд агг . 0 Зафиксируем произвольное кольцо В. О п редел е н не 1. Матрицей размеров тхи (или тхи-матрицей) над кольцом В называют прямоугольную таблицу элементов кольца В, состоящую из т строк и и столбцов. Условимся обозначать матрицы большими латинскими буквами, а их элементы — малыми латинскими буквами с двумя индексами; первый индекс всегда будет номером строки, а второй — номером столбца, в котором расположен рассматриваемый элемент. Например, матрица А размеров т х и с элементами а, подробно запишется в виде: адд адг а2д а22 ад агя а>пд а,„г ...
а Иногда, ради краткости, эту матрицу будем обозначать (а, ) Две матрицы считаются равными, если они имеют одинаковые размеры и одинаковые элементы на соответствующих местах. Множество всех матриц размеров т х и над кольцом В будем обозначать через В Если строку и столбец с номером с' матрицы А обозначить соответственно через А,, А,, то можно записать: ! Ад А = (Ад~Аг Ад) А,„ Укажем некоторые названия и обозначения для отдельных частных видов матриц. 102 называют соответственно верхне- и нижнетреугольными; матрицы ад 0 ...
0 0 аг .. 0 О 0 0 0 ад 0 0 аг 0 0 0 0 а„ 0 0 а 0 0 тх>с 0 0 ... 0 называют диагональными и обозначают в виде Йад(ад,аг» .. ас). ха> где 8 = пддп(т, и). К диагональным матрицам относятся, в частности, нулевая матрица 0 х„(все элементы которой равны нулю) и скалярная матрица йад(а, а,...,а)„„„. Если  — кольцо с единицей е, то в В„„ среди скалярных матриц содержится матрица йад(е, е,..., е)„„„. Она называется единичной и обозначается через Е„х„. Матрицу из В „, в которой элемент на месте (с,~) равен г, а остальные элементы — нули, обозначим через Е 'х„(г) и, в частности, через Е 'х„при г = е. (1,.д) (с >) Индексы т, и у матриц Е„х„,О х„,Е '„„зачастую опускаются. (с з) Введем операции над матрицами. О п р е д е л е н и е 2.
Суммои матриц А = (а;;) удхд и В = (6ц)тха называется матрица С = (сс;),„х„, в которой с,~ — — ас~ + 6,~ для любых с Е 1, т, д е 1, и. Обозначение: А + В = С. Подчеркнем, что сложение определено лишь для матриц одних и тех же размеров над кольцом В. У т в е р ж д е н и е 1. Для любого кольца В множество матриц В„,,„с оиределенной выше оиерацией сложения является абелевой груп иой.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
