algebcodes (1)

Глава 1.

Начальные сведения из теории чисел

1.1. Предварительные замечания

В этой главе представлен даже не минимально достаточный, а минимально необходимый набор элементарных теоретико-число-

вых фактов. Главная цель — наряду с изяществом доказательств основополагающих теорем теории чисел накопить иллюстра-

тивный материал к теории групп, колец и полей. Опущено почти все, что относится к теории делимости, решению сравне-

ний разных степеней, систем сравнений, теории квадратичных вычетов, символов Лежандра и Якоби и т.д.

Опыт показал однако, что безусловная красота теории чисел увлекает молодых людей и побуждает их к расширеннию теоретико-числовых знаний. На первый случай им можно порекомендовать такие источники, как "Основы теории чисел" И.М. Виноградова и "Теория чисел" А.А. Бухштаба.

Итак, считаются известными понятия: наибольшего общего делителя

(a, b) = d,

и наименьшего общего кратного

M(a, b)

двух чисел a и b. Между ними имеется связь

M(a, b) = ab/(a, b).

Каноническое разложение числа a на сомножители имеет

вид

a = pα1 1 pα2 2 . . . pαkk ,

где pi – простое число, αi — натуральное, и это разложение единственно.

Простых чисел бесконечно много. Действительно, если найдены все первые k простых чисел

до pk включительно, то число

p1p2 . . . pk + 1

либо само будет простым, либо любой простой его делитель, деля всю сумму, не будет совпадать ни с одним из чисел (1.1.1).

1.2. Наибольший общий делитель. Алгоритм Эвклида

Разумеется, для определения общего наибольшего делителя

(a, b) = d,

двух целых чисел a и b, a > b можно воспользоваться их каноническими разложениями и выделить их максимальную общую часть. Однако для этой цели существует замечательное средство — алгоритм Эвклида. В теории чисел и алгебре алгоритм Эвклида имеет дело только с вычислением наибольшего

общего делителя d = (a, b) двух чисел a и b. Именно, в чистом виде

Последнее равенство, где rn = 0, неизбежно ввиду уменьшения остатков на каждом следующем шаге деления. Из a = bq0 + r0 следует, что совокупность общих делителей чисел a и b совпадает с совокупностью общих делителей чисел b и r0. Это означает, что (a, b) = (b, r0). На том же основании ((b, r0) = (r0, r1)).

Отсюда последовательно

(a, b) = (b, r0) = (r0, r1) = ... = (rn−1, 0) = rn−1. (1.2.3)

Так как rn = 0, последние три равенства дают

vnrn−1 = r−1,

unrn−1 = r−2, (1.2.13) rn−1(vnun−1 − unvn−1) = (−1)nrn−1.

Умножив первое равенство (1.2.13) на un−1, а второе – на vn−1, вычтем почленно из первого второе. Воспользовавшись третьим равенством (1.2.13), получим окончательно

r−1un−1 − r−2vn−1 = (−1)nrn−1 = (−1)n(r−2, r−1). (1.2.14)

Вспомним, что в наших обозначениях r−2 = a, r−1 = b. Отсюда и получается (1.2.4). Заметим, что равенство (1.2.4) можно получить, и не обращаясь к алгоритму Эвклида (см. задачу 1.6 к данной главе.)

Из равенства (1.2.11) немедленно получается, что (uk, vk) =

1.

Как увидит читатель, алгоритм Эвклида играет важную и интересную роль в проблеме декодирования.

1.3. Сравнения

В связи с данным положительным числом m все целые числа

можно разбить на классы. К одному классу отнесём все целые числа, которые при делении на m дают один и тот же остаток.

Если числа a и b принадлежат к одному классу, то это записывается так

Число m называется модулем. Числа, принадлежащие к одному классу, называются равноостаточными или сравнимыми по модулю m .

Утверждение 1.3.1. Формула (1.3.15) равносильна следующим:

Д о к а з а т е л ь с т в о. Пусть выполнено (1.3.15) Тогда

a = mt1+r, b = mt2+r, 0 ≤< r < m, откуда a−b = m(t1−t2) = mt.

Наоборот, пусть выполняется (1.3.16). Тогда, если b = mt2 + r,

то a = mt2 + mt + r = m(t2 + t) + r = mt1 + r, и a ≡ b(modm)

1.4. Свойства сравнений

Свойства сравнений доказываются в основном свед´ением сравнений к равенствам и наоборот на основании (1.3.15) и (1.3.16) в утверждении 1.3.1.

Утверждение 1.4.1. Два числа, сравнимые с третьим, сравнимы между собой.

Действительно, из a ≡ b(modm) и a ≡ c(modm) следует a =

b+mt1, a = c+mt2, b+mt1 = c+mt2, b−c = m(t2 −t1), b = c + mt3, b ≡ c(modm).

Утверждение 1.4.2. Сравнения можно почленно складывать.

В самом деле,

a1 ≡ b1(modm), . . . , ak ≡ bk(modm),

a1 − b1 = mt1, . . . , ak − bk = mtk,

a1 + . . . + ak = b1 + . . . + bk + m(t1 + . . . + tk),

что и требовалось.

Утверждение 1.4.3. Слагаемые, стоящие в какой-либо части сравнения, можно переносить в другую, меняя знак на обратный.

Действительно, пользуясь утверждением 1.4.2, без ограничения общности, прибавим к сравнению (1.4.17) почленно тривиальное сравнение −bk ≡ −bk(modm). Получим

a1 + . . . + ak − bk ≡ b1 + . . . + bk − bk(modm),

т.е.

a1 + . . . + ak − bk ≡ b1 + . . . + bk−1(modm).

Утверждение 1.4.4. К каждой части сравнения можно прибавить любое целое, кратное модуля.

В самом деле, в силу утверждения 1.4.2 очевидное сравнение mk1 ≡ mk2(modm) можно почленно прибавить к сравнению a ≡ b(modm). В результате a + mk1 ≡ b + mk2(modm), что и требовалось.

Не прибегая к формальным выкладкам, то же самое можно

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

Утверждение 1.4.5. Сравнения можно почленно перемножать.

Действительно, пусть a1 ≡ b1(modm), a2 ≡ b2(modm). Это означает, что a1 = b1 + mt1, a2 = b2 + mt2. Отсюда после перемножения равенств получим a1a2 = b1b2 + mT, т.е. a1a2 ≡ b1b2(modm).

Утверждение 1.4.6. Обе части сравнения можно возводить в одну и ту же степень.

Это простое следствие из утверждения 1.4.5.

Обобщение утверждений 1.4.2, 1.4.5 и 1.4.6 выглядит следующим образом:

Утверждение 1.4.7. Если в выражении целой рациональной функции

∑

S = Axα1 1 xα2 2 . . . xαkk

заменить A на B, xi на yi, такие, что A ≡ B( mod m) xi ≡ yi(modm), то получим:

∑ ∑

Axα1 1 xα2 2 . . . xαkk ≡ By1α1 y2α2 . . . ykαk (modm).

a0xn + a1xn−1 + . . . + an ≡ b0yn + b1yn−1 + . . . + bn(modm).

Утверждение 1.4.8. Обе части сравнения можно разделить на их общий дедитель, если он взаимно прост с модулем.

Пусть

Требование взаимной простоты использовано, и оно существенно. Например:

6 ≡ 18(mod4), но 3 ̸≡9(mod4).

Это были свойства сравнений, аналогичные свойствам равенств.

1.5. Дальнейшие свойства сравнений

Утверждение 1.5.1. Обе части сравнения и модуль можно умножить на одно и то же число.

Последовательно имеем

a ≡ b( mod m), a−b = mt, m1(a−b) = m1mt, m1a = m1b+m1mt.

Это значит

m1a ≡ m1b(modm1m).

Утверждение 1.5.2. Обе части сравнения и модуль можно разделить на их общий делитель.

Утверждение 1.5.3. Если сравнение имеет место по нескольким модулям m1, m2, . . . , mk, то оно имеет место и по модулю, который равен наименьшему общему кратному модулей:

M(m1, m2, . . . , mk).

В самом деле, пусть

a ≡ b(modmi), i = 1, 2, . . . , k; тогда a − b = mit.

Будучи кратным каждого из модулей, разность a −b, кратна и их наименьшего общего кратного.

П р и м е р 1. 1.

812 ≡ 1622(mod6, 9, 15), 812 ≡ 1622(mod90)

Утверждение 1.5.4. Если сравнение имеет место по модулю m, то оно имеет место и по модулю d, равному любому делителю числа m.

Имеем последовательно

a ≡ b(modm), a − b = mt, a − b = m1dt = dt1,

где

t1 = m1t, m = m1d.

Утверждение 1.5.5. Если одна часть сравнения и модуль де-

лятся на какое-нибудь число, то и другая часть сравнения делится на это число.

Действительно, пусть

a ≡ b(modm); тогда a − b = mt.

Если

a = a1z и m = m1z, то a1z−m1zt = b; z(a1−m1t) = b = zb1.

Д о к а з а т е л ь с т в о. Согласно утверждению 1.5.5 совокупность общих делителей чисел a и m совпадает с совокупностью общих делителей чисел b и m. Значит, совпадают и наибольшие общие делители этих чисел, что и требуется.

1.6. Полная система вычетов

Числа, сравнимые по модулю m, образуют класс чисел по мо-

дулю m. Всего имеется m классов; любое число можно представить в виде

mq + r, r = 0, 1, . . . , m − 1.

Любое число класса называется вычетом по модулю m. Вычет, полученный при q = 0, равный самому остатку r, называется наименьшим неотрицательным вычетом. Вычет ρ, самый малый по абсолютной величине, называется абсолютно наи-

Взяв от каждого класса по одному вычету, получим полную систему вычетов по модулю m.

В качестве полной системы вычетов употребляют наименьшие неотрицательные вычеты:

при нечётном m, и

−m2 + 1, . . . , −1, 0, 1, . . . , m2

или

−m2 , . . . , −1, 0, 1, . . . , m2 − 1

при чётном m.

Утверждение 1.6.1. Любые m чисел, попарно несравнимые по модулю m, образуют полную систему вычетов.

Действительно, будучи несравнимыми, они принадлежат различным классам, а так как их m штук, то в каждый класс попадёт в точности по одному числу.

Теорема 1.6.2. Если (a, m) = 1, и x пробегает полную систему вычетов по модулю m, то ax + b, где b произвольное целое, пробегает полную систему вычетов.

Действительно, чисел ax + b столько, сколько чисел x, т.е. m. Покажем, что ax1 + b и ax2 + b несравнимы, если несравнимы x1 и x2. Положим противное, т.е., что

ax1 + b ≡ ax2 + b(modm).

Тогда

ax1 ≡ ax2(modm),

и так как (a, m) = 1, то в силу утверждения 1.4.8 x1 ≡ x2(modm),

что противоречит условию. П р и м е р 1. 2.

Пусть m = 8. a = 11, b = 5, (11, 8) = 1. Полная система вычетов есть 0,1,2,3,4,5,6,7;

11 · 0 + 5 ≡ 5(mod8),

11 · 1 + 5 ≡ 0(mod8),

11 · 2 + 5 ≡ 3(mod8),

11 · 3 + 5 ≡ 6(mod8),

11 · 4 + 5 ≡ 1(mod8),

11 · 5 + 5 ≡ 4(mod8),

11 · 6 + 5 ≡ 7(mod8),

11 · 7 + 5 ≡ 2(mod8).