Коды и математика (рассказы о кодировании) - Аршинов М.Н.
Скачать (прямая ссылка):
Дальнейшее проникновение в проблематику теории кодирования (подробное изучение циклических кодов и их обобщений, знакомство с кодами, исправляющими пакеты ошибок, и специфическими алгоритмами их декодирования и т. д.) требует уже значительно более серьезной математической подготовки. Впрочем, интересующийся читатель может при желании обратиться к литературе, список которой приводится в конце книги. ПРИЛОЖЕН И З
В школьной математике рассматриваются различные операции над числами. Простейшие из них — сложение и обратная к нему операция вычитания, и умножение, для которого обратной операцией яеляєтся деление. Подобные действия приходится производить не только над числами, но и над другими, более сложными объектами. Это можно обнаружить уже и в школьном курсе: на уроках геометрии и физики учат складывать и вычитать векторы, а на уроках алгебры рассматривают операции сложения и умножения многочленов. Однако список таких объектов гораздо обширнее. Мы познакомимся с некоторыми из них, наиболее важными для наших целей.
1. Сравнения и классы вычетов
Исходным материалом для нас остаются пока все же числа. Два целых числа а и Ь называют сравнимыми по модулю п (п — натуральное), если кх разность а — Ь делится на п без остатка *?. Это выражают следующей записью:
a = b (mod п). (1)
Число п называют модулем сравнения (1). Например, 35=2 (mod II), так как разность 35—2=33 делится на 11; аналогично, 25^—11 (mod 9), так как 25—(—!1)=36 делится на 9.
Запись а=0 (mod п) означает тогда, что само число а делится из п, т. е. a=k'ti.
Если зафиксировать некоторый модуль сравнения п, то всякоз натуральное число с можно единственным образом представить в виде
c=kn+r, (2)
где k — частное от деления на п, а г — остаток, совпадающий с одним
*) Понятие сравнимости впервые было введено великим немецким математиком Карлом Фридрихом Гауссом (1777—1855) в его трактате «Арифметические исследования» и является одним из основных понятий теории чисел, ¦ из ч исел
О, I1 2, , , .5 П—1.
(3)
Остаток г называют также вычетом числа с по модулю п. Заметим,-ч то запись вида (2), где (kgrsgn—Ij допускают не только натуральные,-но и любые целые числа. Очевидно, из равенства (2) следует, что с= =? /-(mod я), т. е. всякое число сравнимо со своим остатком (вычетом) по модулю п. Пусть теперь с и & — два произвольных числа, записанные в виде (2):
a=/'1!«+/"!, Ь=к2П+Г2.
Каждый из остатков г1 и T2 — это одно из чисел (3), поэтому их разность может делиться на п лишь в одном случае, когда T1=T2. Но тогда и разность а — Ь= (? — k^n-\-Ti—т2 может делиться нл п тогда и только тогда, когда T1=T2- Отсюда следует, что а==& (mod п) тогда и только тогда, когда числа а и Ь имеют одинаковые остатки при делении На п.
В теории чисел (см., например, [5]) доказывается ряд свойств сравнений, во многом аналогичных свойствам обычных равенств. Подобно тому, как мы это делаем с равенствами, сравнения по одинаковому модулю можно складывать, перемножать и т. д. (так, перемножив сравнения 17=5 (mod 4) и 7=3 (mod 4), получим, как нетрудно убедиться, верное сравнение 119=15 (mod 4). Вообще, если oi=?>i, o2=fr2l to
?j-fe23=6i+62, O1Q2Siijft2.
Значение этих свойств заключается в том, что при рассмотрении вопросов делимости чисел и различных числовых арифметических выражений мы можем входящие в эти выражения числа заменять на другие, сравнимые с ними по данному модулю п; в частности, каждое число может бьпь заменено своим вычетом. Проиллюстрируем сказанное следующей задачей.
Доказать, что число (1981)*+ (1982)* при любом нечетном натуральном k делится па 3.
Замечаем, что 1981=1 (mod 3), 1982=2 (mod 3). Заменяя в исход-пом выражении числа 1981, 1982 их вычетами по модулю 3, получаем
(1981)А+(1982)*= 1+2А (mod 3).
Следовательно, левая часть сравнения делится на 3 тогда и только тогда, когда па 3 делится сумма 1+2*. Для степеней двойки имеем: 23=1, 2?=2, 24ssl, 25=2 и т. д. Вообще, применяя индукцию по убеждаемся, что 2*=1 при k четном и 2Ass2 при k нечетном. Таким образом, при нечетном k
1 + 2А = 1 + 2 =5 О (mod 3), т. е. если к нечетно, то исходное выражение делится на 3.
,118 В разобранной задаче числа 1981 и 1982 могли быть заменены любыми числами а и Ь, дающими при делении на 3 остатки соответственно 1 и 2. Ни утверждение задачи, ни способ его доказательства от этого не изменились бы. Таким образом, в некоторых вопросах все числа, имеющие один и тот же вычет г по модулю п, и, следовательно, сравнимые между собой по этому модулю, оказываются взаимозаменяемыми. Объединим все их в один класс, обозначаемый г:
/- = {с I с = /• (mod «)}. (4)
Иными словами, класс г состоит из всех тех целых чисел, которые записываются в виде (2). Класс, определяемый равенством (4), называют классом вычетов. Каждому вычету 0, 1, 2, . . ., п—1 отвечает свой класс вычетов, так что имеется ровно п различных классов
О, Г, 2, ..., ~1. (5)
Ясно, что эти классы попарно не пересекаются и каждое целой щісло попадает ровно в один класс.
