algebcodes_1

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

Д о к а з а т е л ь с т в о. В условиях теоремы сумма ax + by + c принимает в точности ab значений. Покажем, что они попар-

но несравнимы по модулю ab. Пусть наоборот, нашлись две таких пары x1, y1; x2, y2, что не выполняются сравнения x1 ≡

x2, y1 ≡ y2, но при этом ax1 +by1 +c ≡ ax2 +by2 +c( mod ab). Отсюда имеем последовательно: на основании утверждения 1.4.3

ax1 + by1 ≡ ax2 + by2(modab),

на основании утверждения 1.5.4

ax1 + by1 ≡ ax2 + by2(modb),

на основании утверждения 1.4.4

ax1 ≡ ax2(modb),

а так как (a, b) = 1, то

x1 ≡ x2(modb),

что противоречит условию. Аналогичные выкладки без труда производятся для y1, y2.

1.7. Приведённая система вычетов

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

каждого класса по одному вычету, получим приведённую систему вычетов.

Обычно приведённую систему вычетов выбирают из наименьших неотрицательных вычетов

0, 1, . . . , m − 1.

Обозначим через c количество чисел ряда 0, 1, . . . , m − 1, взаимно простых с m.

Обозначим c = φ(m). Эта функция называется функцией Эйлера.

Имеют место следующие факты:

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

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

простых с модулем, а так как их φ(m) штук, то в каждый класс попадёт в точности по одному числу.

Теорема 1.7.2. Если (a, m) = 1, и x пробегает приведённую систему вычетов по модулю m, то произведение ax также пробегает приведённую систему вычетов.

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

ax1 ≡ ax2(modm).

Тогда, так как (a, m) = 1, то в силу 1.4.8

x1 ≡ x2(modm),

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

Пусть m = 8. a = 11, (11, 8) = 1. Приведённая система вычетов есть 1, 3, 5, 7;

11 · 1 ≡ 3(mod8),

11 · 3 ≡ 1(mod8),

11 · 5 ≡ 7(mod8),

11 · 7 ≡ 5(mod8).

Пусть a = 13, (13, 8) = 1. Получим:

13 · 1 ≡ 5(mod8),

13 · 3 ≡ 7(mod8),

13 · 5 ≡ 1(mod8),

13 · 7 ≡ 3(mod8).

Следствие 1.7.3. Пусть (a, m) = 1, и ax ≡ 1(modm). Тогда, согласно 1.3.16, ax = 1 + mt, ax −mt = 1, и мы получили соотношение вида 1.2.4. Отсюда посредством процедуры раздела 1.2 отыскивается число x.

1.8. Теоремы Эйлера и Ферма

Теорема 1.8.1 (Эйлер). При m > 1 и (a, m) = 1

aφ(m) ≡ 1(modm).

Д о к а з а т е л ь с т в о. Пусть x пробегает приведённую систему вычетов, т.е.

x = r1, r2, . . . , rc; c = φ(m).

Тогда ax1 также пробегает приведённую систему вычетов, быть может, в другом порядке:

ari ≡ ρi(modm).

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

Если ri и ρi принадлежат наименьшим неотрицательным вычетам, а это всегда можно сделать, то обе части сравнения мож-

Теорема 1.8.2 (Ферма). При простом p, и a, не делящемся на p,

ap−1 ≡ 1(modp).

Сравнение

ap ≡ a(modp)

верно при всех a, так как оно верно и при a, делящемся на p.

Стоит показать, что это сравнение справедливо и при a, не делящемся на p. Действительно, из теоремы Ферма получаем

(см. утверждение 1.3.1) ap−1 = tp+1, ap = atp+a = T p+a, ap ≡ a(modp).

1.9.Мультипликативность функции Эйлера

Теорема 1.9.1. Если (a, b) = 1, то φ(ab) = φ(a)φ(b).

Доказательству теоремы предпошлем следующую лемму:

Лемма 1.9.2. Сумма

принимает все значения из привeденной системы вычетов по модулю ab тогда и только тогда, когда x пробегает приведенную систему вычетов по модулю b, а y пробегает приведенную систему вычетов по модулю a.

Д о к а з а т е л ь с т в о. Достаточность Легко видеть, что

Действительно, (ax, b) = 1 по условию, а b|by. Поэтому (ax + by, b) = 1. (В противном случае, т.е. если (ax + by, b) = d > 1, то d|(ax + by), d|b. Отсюда d|by, а значит, d|(ax + by − by), т.е, d|ax, что противоречит тому, что (ax, b) = 1.) Из соображений симметрии также (ax + by, a) = 1. Отсюда следует (1.9.19).

Необходимость. Если в сумме (1.9.18) хотя бы одно x (или также y) не принадлежит приведенной системе вычетов по модулю b, (по модулю a,), то такая сумма не принадлежит приведенной системе вычетов по модулю ab. Действительно, пусть, например, (x, b) = d > 1. Тогда d делит оба слагаемые в (1.9.18), и, следовательно, сумма (1.9.18) не взаимно проста с ab.

Лемма доказана.

Следствие 1.9.3. Сумма (1.9.18) не взаимно проста с ab тогда и только тогда, когда хотя бы одно x (или также y) не принадлежит приведенной системе вычетов по модулю b, (по модулю a,)

Теперь из полной системы вычетов по модулю ab удалим все Z вычетов, не взаимно простых с ab. Останутся ab − Z = φ(ab) вычетов, взаимно простых с ab и только они. Из общего числа ab сумм ax + by удалим те из них, в которых выполняется хотя бы одно из соотношений (x, b) ≠ 1, (y, a) ≠ 1. Их будет ровно

столько же, т.е. Z. Оставшихся ab − Z сумм будет в точности

φ(a)φ(b).

Таким образом, произведение φ(a)φ(b) и число φ(ab) вы-

ражают одну и ту же величину, а потому φ(ab) = φ(a)φ(b), и теорема доказана.

Приведём другое доказательство теоремы 1.9.1. Для этого рассмотрим таблицу

На основании теоремы 1.6.2 числа каждого столбца пробегают полную систему вычетов по модулю a, и, таким образом, в каждом столбце содержится в точности φ(a) чисел, взаимно простых с a. Каждый столбец имеет вид

Числа, взаимно простые с b содержатся в тех и только в тех столбцах, в которых (b, r) = 1. Это означает, что во всех φ(b) столбцах (1.9.21), где (b, r) = 1, и толко в них содержится φ(a)φ(b) чисел, взаимно простых одновременно и с a и с b, а значит, и с их произведением ab. Но всего в таблице (1.9.20) содержится φ(ab) таких чисел. Отсюда φ(ab) = φ(a)φ(b), что и требоваось.

1.10. Вычисление функции Эйлера

Теорема 1.10.1. Пусть

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

где числа

p1, p2, . . . , pk

простые и попарно различные. Тогда

Действительно, среди pαi i чисел 1, 2, . . . , pαi i ровно pαi i−1 чисел делится на pi. Остальные

pαi i − pαi i−1 = pαi i (1 − p1 ) i

чисел не делятся на pi, а значит, взаимно просты с ним и с pαi i . Отсюда и из (1.10.23) получается (1.10.22).

П р и м е р 1. 4.

1). a = 1000 = 2353, φ(1000) = 1000(1 − 1/2)(1 − 1/5) = 400; 2). a = 255 = 3 · 5 · 17, φ(255) = 255(1 − 1/3)(1 − 1/5)(1 −

− 1/17) = 128;

3). a = 13068 = 4 · 27 · 121 = 2233112, φ(13068) = 13068(1 −

−1/2)(1 − 1/3)(1 − 1/11) = (1/2)(2/3)(10/11) = 1980; 4). a = 1001 = 7 · 11 · 13, φ(1001) = 6 · 10 · 12 = 720.

Если бы перед выводом теоремы Эйлера была предложена,

например, задача — найти остаток от деления числа 729720 на 1001 — она могла вызвать недоумение. На самом деле 1001 = = 7 · 11 · 13, φ(1001) = 720, (729, 1001) = 1, 729720 ≡ 1(mod 1001).

1.11. Первообразные корни

При (a, m) = 1 существуют положительные целые числа γ с условием

Например, (теорема Эйлера)

aφ(m) ≡ 1(modm).

Определение 1.11.1. Наименьшее из чисел γ, удовлетворяющее (1.11.24) называется показателем, которому a принадлежит по модулю m.

П р и м е р 1. 5.

21 = 2 ≡ 2(mod5),

22 = 4 ≡ 4(mod5),

23 = 8 ≡ 3(mod5),

24 = 16 ≡ 1(mod5).

Таким образом, 4 – есть показатель, которому 2 принадлежит по модулю 5, φ(5) = 4.

В то же время

51 = 5 ≡ 5(mod12),

52 = 25 ≡ 1(mod12).

Таким образом, число 2 – есть показатель, которому 5 принадлежит по модулю 12, хотя φ(12) = 4. Более того, все элементы приведённой системы вычетов по модулю 12 принадлежат показателю 2.

Утверждение 1.11.2. Если a по модулю m принадлежит по-

казателю δ, то числа 1 = a0, a, . . . , aδ−1 попарно несравнимы по модулю m.

Действительно, из сравнения al ≡ ak(modm), (0 ≤ k < l < δ)

следовало бы al−k ≡ 1(modm), (0 ≤ l − k < δ), что противоречит определению величины δ : ведь δ есть наименьшее из чисел γ, для которых aγ ≡ 1(modm).

Утверждение 1.11.3. Если a по модулю m принадлежит показателю δ, то aγ1 ≡ aγ2 ( mod m) тогда и только тогда, когда

γ1 ≡ γ2(modδ), т.е. γ1 − γ2 = δt.

Сначала перед доказательством приведем П р и м е р 1. 6.

21 = 2 ≡ 2(mod15),

22 = 4 ≡ 4(mod15),

23 = 8 ≡ 8(mod15),

24 = 16 ≡ 1(mod15).

Таким образом, число 2 принадлежит показателю δ = 4 по модулю 15.

Далее

25 = 32 ≡ 2(mod15), 5 ≡ 1(mod4), 26 = 64 ≡ 22(mod15), 6 ≡ 2(mod4), 27 = 128 ≡ 23(mod15), 7 ≡ 3(mod4), 28 = 256 ≡ 20(mod15), 8 ≡ 0(mod4).

Иначе говоря, сравнимость последовательных степеней числа a, принадлежащего показателю δ, наступает с периодично-

стью δ.

Доказательству предпошлем следующее построение. Пусть r1 и r2 – наименьшие неотрицательные вычеты по модулю δ; r1 < δ, r2 < δ, тогда при некоторых q1 и q2 имеем γ1 = δq1 + r1, γ2 =

δq2 + r2. Отсюда и из сравнения aδ ≡ 1(modm) получаем

aγ1 = (aδ)q1 ar1 ≡ ar1 (modm), aγ2 = (aδ)q2 ar2 ≡ ar2 (modm).

(1.11.25) Д о к а з а т е л ь с т в о. Необходимость. Пусть aγ1 ≡

aγ2 (modm).

Тогда ar1 ≡ ar2 (modm), и в силу утверждения 1.11.2 r1 = r2 = r, (так как в противном случае ar1 и ar2 были бы несравнимы), а потому γ1 = δq1 + r, γ2 = δq2 + r, т.е. γ1 ≡ γ2(modδ).

Достаточность. Пусть γ1 ≡ γ2(modδ). Тогда r1 = r2, и из (1.11.25) получаем, что aγ1 ≡ aγ2 (modm). Теорема доказана.

Имеем далее

aφ(m) ≡ 1(modm).

т.е.

aφ(m) ≡ a0(modm).

Отсюда и из предыдущего рассуждения следует, что

φ(m) ≡ 0(modδ).

Таким образом, справедливо

Утверждение 1.11.4. Показатели, которым числа принадлежат по модулю m, суть делители числа φ(m). Наибольший из этих делителей есть само φ(m).

Определение 1.11.5. Числа, принадлежащие показателю φ(m), называются первообразными корнями по модулю m,

(если они существуют).

Иначе говоря, a будет первообразным корнем по модулю m, когда ни при каком ε < φ(m) не выполняется сравнение

aε ≡ 1(modm).

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

m = 2, 4, pn, 2pn.

Доказательство этого факта здесь опущено. Читатель найдёт его в руководствах по теории чисел.

Утверждение 1.11.6. В приведенной системе вычетов по модулю m количество чисел, принадлежащих показателю δ, есть

φ(δ.)

Действительно, покажем, что если a принадлежит показателю δ по модулю m, и (γ, δ) = 1, то aγ также принадлежит показателю δ по модулю m.

Предположим противное, т.е., что (aγ)δ1 ≡ 1(modm), где δ1 < δ. Тогда, согласно утверждению 1.11.3, γδ1 ≡ 0(modδ). В свою очередь это означает, что γδ1 делится на δ, что противоречит условию δ1 < δ, а потому δ1 = δ, что и требовалось.

Пусть теперь (γ, δ) = d > 1. Положим δ/d = δ1 < δ. Тогда

(aγ)δ1 = (aγ) d = (aδ) d = 1. Это означает, что a принадлежит показателю δ1 < δ по модулю m.

В частности, из утверждения 1.11.6 следует, что число первообразных корней есть

φ(c) = φ(φ(m)).

Пусть c = φ(m), и q1, q2, . . . , qk – различные простые делители числа c.

Утверждение 1.11.7. Для того, чтобы g, взаимнопростое с m, было первообразным корнем по модулю m, необходимо и до-

статочно, чтобы g не удовлетворяло ни одному из сравнений

c

g qi ≡ 1(modm).

Д о к а з а т е л ь с т в о. Необходимость. Если

c

g qi ≡ 1,

то c = φ(m) не показатель, которому принадлежит g по модулю m.

Достаточность. Пусть не выполняется ни одно из срав-

c

нений g qi ≡ 1(modm), и пусть показатель δ < c. Тогда c/δ –

целое, и пусть c/δ = qt, c/q = δt, gδt = (gδ)t ≡ 1 mod m. Это

значит, gc/q ≡ 1 mod m, что противоречит условию.

Более простое доказательство этого факта получается из элементарных сведений о циклических группах (см. след. гл.)

1.12. Индексы

Пусть p− простое нечетное, n ≥ 1, m – одно из чисел 2, 4, p, 2pn и пусть c = φ(m).

Пусть g — первообразный корень по модулю m. Заметим,

что (g, m) = 1, так как g принадлежит приведенной системе вычетов по модулю m.

Утверждение 1.12.1. Если γ пробегает полную систему наименьших неотрицательных вычетов γ = 0, 1, . . . , c −1 по модулю c, то gγ пробегает приведенную систему вычетов по модулю m.

Д о к а з а т е л ь с т в о. gγ пробегает c чисел взаимнопростых с m, так как (g, m) = 1. Остается применить утверждение 1.11.2.

Определение 1.12.2. Пусть (a, m) = 1. Если a ≡ gγ(mod m), то γ называется индексом числа a по модулю m при основании g и обозначается

γ = indg a.

Ввиду утверждения 1.12.1 всякое такое a, что (a, m) = 1, имеет единственный индекс γ0 среди чисел γ = 0, 1, . . . , c − 1.

В самом деле, если одновременно

a ≡ gγ1 (modm),

и

a ≡ gγ2 (modm),