Коды и математика (рассказы о кодировании) - Аршинов М.Н.
Скачать (прямая ссылка):
е, g, g2.....g""1.
Мы доказали, что порядок конечной циклической группы совпадает с порядком ее образующего. Как, используя сказанное, вывести из теоремы Лагранжа следующие утверждения:
а) порядок любого элемента конечной группы является делителем порядка этой группы;
б) всякая группа простого порядка является циклической?
*) В случае, если групповая операция—сложение, приходится говорить не о степенях; а о кратных элемента.
,13812. Найдите возможные порядки элементов в группах S3, S5, циклической группе порядка 12.
13. Проверьте, что всякая подгруппа H циклической группы G = (g) сама является циклической.
Указание: рассмотрите наименьшую положительную степень gk ? Н, покажите, что H = (gk).
14. Покажем, пользуясь законом дистрибутивности, что нулевой элемент аддитивной группы кольца играет роль нуля и при умножении.
Рассмотрим произведение любых двух элементов а и b и преобразуем его следующим образом:
Второе слагаемое, как видно из равенства, играет роль нейтрального элемента при сложении. В силу его единственности Ой = 0 для всякого b ? К.
15. Какие из следующих числовых множеств являются кольцами относительно обычных операций сложения и умножения:
а) множество четных чисел;
б) множество чисел, кратных данному п;
в) множество многочленов степени <п с действительными коэффициентами;
г) множество всех многочленов с целыми коэффициентами;
д) множество неотрицательных действительных чисел;
е) множество всех чисел вида а-\-Ь |^2,гдеаий—рациональные.
В каких случаях мы имеем дело с кольцом с единицей, в каких— с полем?
16. Покажем, [что делитель нуля (левый или правый) не может быть обратим. В самом деле, пусть ха=\ и ab = Q. Тогда
Следовательно, Ь = 0 и а не является делителем нуля.
Из сказанного непосредственно вытекает, что никакое поле не содержит делителей нуля.
17. Показать, что если п = Пі-п2— число составное, то %п не является полем.
18. Показать, что ненулевой элемент k?zn обратим тогда и только тогда, когда числа k и п взаимно просты, и что в противном случае k является делителем нуля.
19. Пользуясь предыдущим утверждением, найдите обратимые элементы и делители нуля в кольцах вычетов 2е. Zs> 2її, Zi2. Для обратимых элементов найдите обратные. Для элементов к, явля-
ab = (я-j-O) & = ufi + 0&.
xab =
{
(ха) ¦b = \-b = b, X (ab)=x-0 = 0.
,139ющихся делителями нуля, найдите т ф О такой, что к-т = 0. Является ли такой класс m единственным?
20. Уже самые простые сведения о кольцах и группах могут быть применены в различных математических вопросах. Прекрасной иллюстрацией этого является теория чисел. Рассмотрим, например, хорошо известную теорему (малую теорему Ферма):
Если р — простое, то для любого натурального а число аР—а делится на р.
Рассуждаем так:
аР—а = а 1).
Если а делится на р, то утверждение очевидно.
Пусть а не делится на р и а = тр-\-г (0 < r^p—1). Тогда в поле вычетов Wip а?г и г ф O, Делимость числа аР~г—1 на р равносильна тому, что в %р справедливо равенство rP~l — T = O или равносильное ему
-1 = Т. (4 ^
Так как порядок мультипликативной группы поля Zp равен р—1, то из теоремы Лагранжа вытекает справедливость равенства (4), и это доказывает малую теорему Ферма.
21. Подумайте (это не простая задача), как с помощью указанных методов можно доказать утверждение: если р — простое, то (р—1)! + 1 делится на р. Это теорема Вильсона, одна из наиболее изящных теорем элементарной теории чисел.
22. Функция Эйлера (р (п) определяется в теории чисел как количество натуральных чисел, меньших п и взаимно простых с ним. Например, ф(4) = 2, ср(8) = 4 и т. д. Для всякого простого р очеви-дноф(р) = р—1. Обобщением малой теоремы Ферма является теорема Эйлера, которая формулируется так:
Для любого натурального а, взаимно простого с п, a® M — 1 делится на п. Например, при п = 8, а = 5 имеем 54—1 =624 = 8x78. Можно предложить следующий план доказательства теоремы Эйлера (детали — на усмотрение читателя):
а) показать, что множество обратимых элементов любого кольца образует группу относительно умножения;
б) рассмотреть кольцо вычетов Jin и убедиться, что группа его обратимых элементов имеет порядок ф (п) (вспомните утверждение пункта 18);
в) дальнейшие рассуждения таковы же, как и при доказательстве малой теоремы Ферма.
23. Найти все решения системы линейных уравнений
*+2z=l, i/ + 2z = 2, 2* + z=l в поле вычетов: а) по модулю 3; б) по модулю 5,
,14024. Многочлен P(X) ^f(X) называется неприводимым, если не существует разложения р (X) = / (X) g (X), в котором / (X), g (X) ? [X] и степени сомножителей меньше, чем степень многочлена P (X).
Выяснить, являются ли следующие многочлены: Х3 + Х2+1, Х*+Х2+1, Х2 — 2
неприводимыми над полем: a) Il2', б) Z3; в) Q', г) R-
25. Разложить на неприводимые множители многочлен
Х* + Х* + Х + 1
дад полем: a) Z2', б) Z3; в) Q.
26. Найти наибольший общий делитель многочленов
/(Х) = Х3 + Х2 + 2Х + 2; S(X)=X2 + *+1'
над полем: a) Z3! б) Q.