algebra.1semestr.lectures1-16.

Следующая теорема утверждает, что функция Эйлера мультипликативна.

Теорема 40. Если (a; b) = 1, то '(ab) = '(a) ¢ '(b).

Доказательство. Расположим числа от 1 до ab в виде прямоугольника b £ a:

(b ¡ 1)a + 1 (b ¡ 1)a + 2 : : : ba

По только что доказанной лемме мы должны посчитать, сколько чисел в нашем прямоугольнике взаимно просто и с a и с b. Посмотрим сначала, где размещаются числа взаимно простые с a. В первой строке таблицы (по определению функции Эйлера) таких чисел ровно '(a). Заметим, что для фиксированного столбца либо все числа в нем взаимно просты с a, либо ни одно из них не взаимно просто с a (так как НОД(i; a) = НОД(i + ka; a)). Итак, все числа в нашей таблице взаимно простые с a занимают '(a) столбцов.

Аналогично, все числа в таблице взаимно простые с b занимают '(b) строк. Необходимые нам числа располагаются на пересечении выбранных строк и столбцов, поэтому их количество равно '(a) ¢ '(b). ¤

Из этой теоремы и утверждения о представимости любого числа в виде произведения

Доказательство. Первое равенство вытекает из уже установленных свойств функции Эй-

Теорема 42. (Теорема Эйлера). Если a и n взаимно простые натуральные числа, то a'(n) ´ 1 (mod n).

Доказательство. Пусть x1; : : : ; x'(n) все числа · n взаимно простые с n. Пусть ri обозначает остаток при делении axi на n. Поскольку a взаимно просто с n, то множество fr1; : : : ; r'(n)g совпадает с множеством fx1; : : : ; x'(n)g (но порядок элементов может быть разный!).

Поскольку axi ´ ri (mod n), то получаем

Поскольку a взаимно просто с каждым из xi, последовательно сокращая, мы получаем a'(n) ´ 1 (mod n).

11

Используя эту теорему, вычислим остаток при делении 5130 на 48. Поскольку 5 и 48 взаимно, просты и '(48) = 16, то по теореме Эйлера 516 ´ 1 (mod 48). Так как 130 = 8¢16+2, то 5130 = (516)8 ¢ 52 ´ 25 (mod 48). ¤

Следствие 43. (Малая теорема Ферма).8 Если p простое число не делящее a, то ap¡1 ´ 1 (mod p).

Доказательство. Возьмем n = p в теореме Эйлера и заметим, что '(n) = '(p) = p ¡ 1. ¤

Мы знаем, как решать простые сравнения целых чисел. Сейчас мы рассмотрим некоторые специальные системы сравнений.

Теорема 44. (Китайская теорема об остатках). Пусть n1; : : : ; nk попарно взаимно простые (то есть (ni; nj) = 1 для i =6 j) натуральные числа и c1; : : : ; ck 2 Z. Тогда система сравнений x ´ ci (mod ni), i = 1; : : : ; k имеет целое решение x0, причем это решение единственно по модулю n = n1 ¢ : : : ¢ nk.

Доказательство. Обозначим mj = n=nj. Из (mj; nj) = 1 вытекает, что сравнение mjxj ´ cj (mod nj) имеет решение (выберем любое решение). Мы утверждаем, что x = m1x1 + ¢ ¢ ¢ + mkxk является решением всей системы сравнений.

Действительно, рассмотрим j-ое сравнение. Тогда mjxj ´ cj (mod nj) и mixi ´ 0 (mod nj), поскольку mi делится на nj (докажите это!). Итак x ´ cj (mod nj)

Чтобы проверить единственность, предположим, что y другое решение нашей системы сравнений. Тогда для любого j получаем x0 ´ y (mod nj), следовательно nj j x0 ¡ y. Поскольку все ni попарно взаимно просты, то n = n1 ¢: : :¢nk делит x0 ¡y, то есть y 2 x0 +nZ.

Кроме того, если y 2 x0 +nZ, то нетрудно проверить (сделайте это!), что y удовлетворяет

8Существует еще великая теорема Ферма. Она утверждает, что если n > 3, то уравнение xn + yn = zn не имеет решения в целых числах. Ферма утверждал, что нашел короткое доказательство этой теоремы, но не записал его из-за недостатка места. Только в 90-х годах XX века английский математик Эндрю Уайлс сумел установить этот результат, используя мощные методы современной теории чисел.

12

77 ¢ 1 + 55 ¢ 4 + 35 ¢ 2 = 77 + 220 + 70 = 367 удовлетворяет нашей системе, следовательно общее решение записывается в виде x = 367 + 385Z.

¤

4.1. Алгебраические операции. Пусть M некоторое множество. Бинарная операция на M это отображение f, которое ставит в соответствие данной паре элементов a; b 2 M элемент c = f(a; b) 2 M (результат выполнения операции). Часто вместо символа f для обозначения операции используется символ ±, который ставится между элементами: c = a±b.

Например, + и £ бинарные операции на множестве целых чисел, а также на множествах Q; R. Другой пример бинарной операции на Z это возведение в степень: a ± b = ab.

Рассмотрим некоторые (привычные нам) свойства бинарных операций. 1) Коммутативность, то есть a ± b = b ± a для всех a; b 2 M.

Например, операции сложения и умножения целых чисел коммутативны, а операция возведения в степень нет. Например, 2 ± 3 = 23 = 8, но 3 ± 2 = 32 = 9.

2). Ассоциативность, то есть (a ± b) ± c = a ± (b ± c) для всех a; b; c 2 M.

Например, операции сложения и умножения действительных чисел ассоциативны. Рассмотрим операцию возведения в степень. Имеем (2 ± 3) ± 2 = (23)2 = 26, но 2 ± (3 ± 2) = 29, поэтому эта операция не ассоциативна.

Теорема 46. Если операция ± ассоциативна, то, при любой расстановке скобок в выражении a1 ± ¢ ¢ ¢ ± an, результат будет один и тот же.

5. Лекция 5

L5

Пусть a1 ± ¢ ¢ ¢ ± an обозначает a1 ± (a2 ± : : : (an¡1 ± an)), такую расстановку скобок будем называть стандартной. Например, a1 ± a2 ± a3 обозначает a1 ± (a2 ± a3).

Предложение 47. Если ± ассоциативная операция, то для любого i = 1; : : : ; n выполняется

(a1 ± : : : ai) ± (ai+1 ± ¢ ¢ ¢ ± an) = a1 ± ¢ ¢ ¢ ± an :

Доказательство. Индукция по n ¸ 3. При n = 3 возможны два случая. Если i = 1, то расстановка скобок в левой части стандартная.

Если же i = 2, то левая часть имеет вид (a1 ± a2) ± a3, и нужное равенство вытекает из ассоциативности.

Предположим, что n > 3, и мы уже проверили наше утверждение для всех чисел меньших

n.

Если i = 1, то выражение a1 ¢ (a2 ± ¢ ¢ ¢ ± an) имеет стандартную расстановку скобок. Итак, допустим, что i ¸ 2. Тогда, по тождеству ассоциативности,

13

(a1 ± : : : ai) ± (ai+1 ± ¢ ¢ ¢ ± an) = (a1 ± (a2 : : : ai)) ± (ai+1 ± ¢ ¢ ¢ ± an) = a1 ± ((a2 : : : ai) ± (ai+1 ± ¢ ¢ ¢ ± an))

Но число сомножителей в произведении (a2 : : : ai) ± (ai+1 ± ¢ ¢ ¢ ± an) равно n ¡ 1. Поэтому, по предположению индукции, последнее выражение равно a2 ± ¢ ¢ ¢ ± an, следовательно

Теорема 48. Если ± ассоциативная операция, то любая расстановка скобок в выражении a1 ± ¢ ¢ ¢ ± an приводит к одинаковому результату.

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

(a1 ± ¢ ¢ ¢ ± ai) ± (ai+1 ± ¢ ¢ ¢ ± an) :

По индукции, можно считать, что в произведениях a1 ±¢ ¢ ¢±ai и ai+1 ±¢ ¢ ¢±an расстановка скобок стандартная. Осталось применить предыдущее предложение. ¤

Определение 49. Элемент e 2 (M; ±) называется нейтральным (или единицей), если a ± e = e ± a = a для любого a 2 M.

Например, 0 нейтральный элемент (Z; +), и 1 нейтральный элемент (Z; ¢). С другой стороны (Q+; +) (множество положительных рациональных чисел) не содержит нейтрального элемента.

Предложение 50. Если нейтральный элемент существует, то он единственен.

Доказательство. Пусть e1; e2 нейтральные элементы в M, и мы докажем, что e1 = e2. Поскольку e1 нейтрален, то e1 ± x = x для любого x 2 M. Подставляя в это равенство

Предположим теперь, что (M; ±) имеет нейтральный элемент e. Назовем элемент b 2 M обратным к a (и пишем b = a¡1), если выполняются равенства a ± b = b ± a = e.

Например, любой элемент в (Z; +) обратим: обратным к n будет элемент ¡n. С другой стороны, только §1 имеет обратный в (Z; ¢). В (Q; ¢) ситуация лучше: если q 6= 0, то его обратным является элемент 1=q, а 0 не обратим.

Предложение 51. Если ± ассоциативна и a¡1 существует, то он единственен.

Доказательство. Предположим, что b1 и b2 обратные к a. В частности b1 ± a = e и a ± b2 = e. Используя ассоциативность, получаем

b1 = b1 ± e = b1 ± (a ± b2) = (b1 ± a) ± b2 = e ± b2 = b2 :

¤

14

5.1. Кольца вычетов по модулю m. Напомним, что все классы вычетов по модулю m исчерпываются списком 0, 1, . . . , m ¡ 1. Обозначим это множество через Zm (или Z=mZ смысл такой "дробной" записи станет ясен позднее).

Заметим, что если a1; : : : ; am полная система представителей по модулю m, то Zm = fa1; : : : ; amg.

Введем теперь на множестве Zm операции сложения и умножения. А именно положим a + b = a + b и a ¢ b = ab.

Заметим, что это определение корректно, то есть не зависит от выбора конкретных представителей в классах a и b. Проверим это утверждение для суммы (проделайте соответствующие вычисления для произведения самостоятельно!).

Предположим, что a1 2 a и b1 2 b другие представители смежных классов, и мы должны доказать, что a + b = a1 + b1. Действительно, a1 2 a влечет a ´ a1 (mod m); аналогично b ´ b1 (mod m). Но тогда, как мы уже доказывали, a + b ´ a1 + b1 (mod m), следовательно a + b = a1 + b1.

Например, используя определение операций, легко выписать таблицы сложения и умно-

Заметим, что 0 нейтральный элемент в (Zm; +), а 1 нейтральный элемент в (Zm; ¢). В случае Z3, как нетрудно увидеть из таблицы, все ненулевые элементы обратимы.

Предложение 52. Класс вычетов a обратим в Zm тогда и только тогда, когда (a; m) = 1.

Доказательство. ). Если a¢b = 1, то ab ´ 1 (mod m), то есть m j ab¡1. Тогда ab¡1 = mx для некоторого x 2 Z, следовательно ab + m(¡x) = 1, а это доказывает взаимную простоту a и m.

(. Поскольку a и m взаимно просты, то существуют целые u; v такие, что au + mv = 1. Сравнивая по модулю m, получаем a ¢ u = 1, то есть u является обратным к a в Zm. ¤

Следствие 53. Все ненулевые элементы Zm обратимы тогда и только тогда, когда m простое число.

Доказательство. ). Иначе m = kl для целых k; l > 1. Поскольку НОД(k; m) = k 6= 1, то k не обратим.

(. Если 0 < k < p, то k взаимно прост с p, поэтому элемент k 2 Zm обратим. ¤

Следствие 54. Число обратимых элементов в Zm равно '(m).

Например, найдем обратный к элементу 3 в Z7 (поскольку (3; 7) = 1, то обратный существует). Последовательно умножая 3 ¢ 1 = 3, 3 ¢ 2 = 6, : : : , находим, что 3 ¢ 5 = 15 = 1, поэтому 5 обратный к 3.

Заметим, что линейное сравнение ax ´ b (mod m) можно рассматривать как (линейное) уравнение в кольце Zm. Как мы видели выше это уравнение не имеет решений, если d =

15

НОД(a; m) не делит b, и имеет бесконечное число решений в противном случае (по крайне мере, если d > 1).

¹

Пример 55. Рассмотрим уравнение 4x = 2 в Z6, то есть сравнение 4x ´ 2 (mod 6). Оно эквивалентно сравнению 2x ´ 1 (mod 3). Поскольку x0 = 2 удовлетворяет этому уравнению, то его общее решение есть 2 + 3Z. Этот класс распадается на два (непересекающихся) класса по модулю шесть: 2 + 6Z и 5 + 6Z.

Итак, 2 и 5 все решения уравнения 4x = 2 в Z6.

Заметим, что (Zm; +) удовлетворяет тождествам коммутативности и ассоциативности, имеет нейтральный элемент, и каждый элемент обладает обратным. (Zm; ¢) также коммутативно и ассоциативно. Кроме того, эти две операции связаны тождеством дистрибутивности: a(b + c) = ab + ac для любых a; b; c 2 Zm. Поэтому мы говорим, что Zm кольцо.

5.2. Комплексные числа. Уравнение x2 = ¡1 не имеет решения в действительных числах. Чтобы исправить эту ситуацию мы добавим к R символ (мнимой единицы) i и наложим соотношение i2 = ¡1 (то есть i корень уравнения x2 + 1 = 0). Чтобы расширить действия операций + и ¢ на новые (комплексные) числа, мы должны разрешить выражения вида z = a+bi, где a; b 2 R. Попытаемся определить операции на комплексных числах. При этом мы воспринимаем i как переменную и приводим подобные:

(a + bi) + (c + di) = (a + c) + (b + d)i :

Ясно (проверьте!), что эта операция ассоциативна и коммутативна, 0 = 0 + 0 ¢ i нейтральный элемент, и любой элемент z = a + bi имеет обратный: ¡z = ¡a + (¡b)i. Чтобы определить операцию умножения, раскроем скобки и используем соотношение i2 = ¡1:

(a + bi) ¢ (c + di) = ac + adi + bci + bdi2 = (ac ¡ bd) + (ad + bc)i :

Например, (2+i)(3¡i) = 6¡2i+3i+1 = 7+i. Можно проверить (проделайте вычисления!), что операция умножения комплексных чисел коммутативна и ассоциативна, имеет единицу 1 = 1 + 0 ¢ i, и выполнено тождество дистрибутивности. Итак, множество комплексных чисел C образует кольцо. Более того, любой ненулевой элемент z = a + bi имеет обратный z¡1 = a=(a2 + b2) ¡ b=(a2 + b2)i, поэтому C поле.

Заметим также, что R содержится в C: элемент a 2 R можно рассматривать как комплексное число a + 0 ¢ i.

Для каждого комплексного числа z = a + bi определим его сопряженное z = a ¡bi. Тогда выполнено следующее:

1) z = z.

Действительно, z = a ¡ bi = a + bi = z.

2)z + z = 2a 2 R.

3)z = z если и только если z 2 R.

Действительно, равенство a + bi = a ¡ bi эквивалентно bi = ¡bi, то есть b = 0.

4)z1 + z2 = z1 + z2 и z1 ¢ z2 = z1 ¢ z2 (проведите необходимые вычисления!).

5)z ¢ z = (a + bi)(a ¡ bi) = a2 + b2 неотрицательное действительное число.

16

Корень из этого числа jzj = pa2 + b2 называется модулем комплексного числа z. В частности jzj = 0 только для нулевого z.

Эти свойства комплексного сопряжения используются для вычислений.

Пример 56. Вычислить 21 ¡+ ii.

Решение. Домножим числитель и знаменатель этой дроби на сопряженное к 1 + i:

¤

6. Лекция 6

L6

Из сказанного выше вытекает, что комплексные числа можно определить как пары (a; b) действительных чисел, операции на которых задаются следующими правилами:

1)сложение (a; b) + (c; d) = (a + c; b + d);

2)умножение (a; b) ¢ (c; d) = (ac ¡ bd; ad + bc).

Действительное число a может быть отождествлено с парой (a; 0) 2 C, то есть можно считать, что R µ C.

Замечание 57. Операции сложения и умножения на R индуцированы соответствующими операциями на C.

Доказательство. Пусть a; b действительные числа, и a + b их сумма. При вложении R µ C число a перейдет в (a; 0), b в (b; 0), и a + b в (a + b; 0).

Складывая (a; 0) и (b; 0) в C, получаем (a + b; 0), тот же результат.

Аналогично, перемножая (a; 0) и (b; 0) в C (по определению умножения) получаем (проверьте!) (ab; 0), что является образом произведения a и b в R. ¤

Как мы уже отмечали, множество комплексных чисел (C; +; ¢) с только что введенными операциями сложения и умножения является полем. Из алгоритма обращения ненулевого элемента C вытекает следующая простая формула деления.

Замечание 58. Если z = a + bi, 0 6= z1 = c + di комплексные числа, то

6.1. Тригонометрическая форма комплексного числа. Представим комплексное число z = a + bi вектором на плоскости с началом в начале координат и концом в точке с координатами (a; b).

a

17

Длина этого вектора обозначается через r, а угол между осью OX и направлением вектора обозначается через ', и называется аргументом z, arg z. Заметим, что ' определен с точностью до целого кратного 2¼ (полного оборота), то есть определен однозначно, если наложить ограничение 0 · ' < 2¼. Кроме того, аргумент нулевого вектора не определен.

Рассматривая прямоугольный треугольник с катетами a, b и гипотенузой r, сразу же получаем

Предложение 59. Если z = a + bi, то jzj = r = pa2 + b2. Кроме того, cos ' = a=r, sin ' = b=r, то есть a + bi = z = r(cos ' + i sin '). Такая форма записи называется триго-

Из определения сложения вытекает, что комплексные числа складываются как вектора (по правилу параллелограмма).

z1±+ z2 j;

j j jwww² z1 ²±Gj j j wwwwwww² ²

²²²²² wwwwwwwjjj4±² z² 2 ²²wwwwjjjjjj

²²wjjj

±wjj

Мы дадим геометрическую интерпретацию операции умножения комплексных чисел.

Предложение 61. Если z = r(cos '+i sin ') и z1 = r1(cos '1+i sin '1), то zz1 = rr1[cos('+ '1) + i sin(' + '1)].

Итак, при перемножении комплексных чисел их длины (модули) перемножаются, а углы (аргументы) складываются.

Доказательство. Раскрывая скобки в произведении и приводя подобные, получаем (проделайте вычисления!)

Следствие 62. (теорема Муавра). Если z = r(cos ' + i sin '), то zn = rn(cos n' + i sin n').

Эта формула позволяет быстро вычислять степени комплексных чисел.

Пример 63. Найти (3 + p3 i)10.

Решение. Как мы же установили z = 2p3 (cos ¼=6 + i sin ¼=6), поэтому

18

¤

Заметим, что если jzj = r, z лежит на окружности радиуса r с центром в начале координат. В частности все комплексные числа с модулем 1 лежат на единичной окружности.

Предложение 64. (сравнение модулей комплексных чисел) Пусть z1; z2 и 0 =6 z3 комплексные числа. Тогда

1)jz1z2j = jz1j ¢ jz2j;

2)jz1j < jz2j влечет jz1z3j < jz2z3j;

3)jz1j ¡ jz2j · jz1 + z2j · jz1j + jz2j.

Доказательство. 1) вытекает из формулы произведения.

2). Поскольку jz3j > 0, то утверждение вытекает из 1) и свойств действительных чисел. 3). Неравенство jz1 + z2j · jz1j+ jz2j вытекает из вышеприведенного рисунка (сумма двух

сторон треугольника не меньше третьей стороны). Применяя это неравенство, получаем

6.2. Извлечение корней в C.

p

Определение 65. u 2 C называется корнем n-ой степени из z 2 C (и обозначается n z), если un = z.

p

Например, нетрудно видеть, что n 0 имеет единственное значение 0. В поле комплексных чисел уравнение un = z может иметь больше корней, чем в R. Например, уравнение z4 = 1 имеет только два корня §1 в R, но четыре корня §1; §i в C. Позже мы увидим, что этим списком исчерпываются все комплексные корни данного уравнения.

Теорема 66. Корень n-ой степени из комплексного числа 0 =6 z = r(cos ' + i sin ') имеет ровно n значений

Числа Ek называются (комплексными) корнями n-ой степени из единицы.

Доказательство. Мы докажем наше утверждения для случая корней из единицы. Итак, пусть z = r(cos '+i sin ') удовлетворяет уравнению zn = 1. Тогда 1 = j1j = jznj = rn, где 0 < r действительное число. Нетрудно видеть (докажите это!), что единственной возможностью является r = 1. Итак z = cos ' + i sin ', следовательно zn = cos n' + i sin n' = 1. Из этого вытекает, что cos n' = 1 и sin n' = 0.

Использование элементарной геометрии завершает рассуждение (проделайте необходимые выкладки!). ¤

19

Заметим, что n комплексных корней n-ой степени из 1 располагаются в вершинах правильного n-угольника вписанного в единичную окружность так, что одна вершина попадает в точку (1; 0). Например (при n = 4), правильный квадрат, вписанный в единичную окружность выглядит так:

O

±ÄÄÄÄÄÄÄÄiı:?????????± / ¡1?????????±ÄÄÄÄÄÄÄÄÄ1

¡i

Поэтому §1; §i все комплексные корни четвертой степени из 1.

Аналогично, вписывая в единичную окружность правильный треугольник, мы находим три кубических корня из единицы: 1, " = ¡1=2 + ip3=2 и " = "2 = ¡1=2 ¡ ip3=2 (проведите необходимые вычисления!).

Заметим, что E1k = Ek для k < n и E1n = 1. Выведем отсюда простое правило умножения корней.

случае k + l ¸ n мы также получаем Ek ¢ El = E1k+l. Поскольку E1n = 1 и n · k + l < 2n, то последнее выражение равно Ek+l¡n. ¤

Следствие 68. Множество всех комплексных корней n-ой степени из 1 образует группу относительно умножения.

Доказательство. Замкнутость относительно умножения вытекает из только что доказанной формулы. Ясно, что 1 = E0 является нейтральным элементом в нашем множестве. Осталось проверить наличие обратного элемента.

Но равенство Ek ¢En¡k = 1 влечет, что корень En¡k обратный элемент к корню Ek. ¤

Определение 69. Корень n-ой степени из единицы Ek называется примитивным, если любой другой корень El равен некоторой степени Ek.

Поскольку E1k = Ek, то E1 примитивный корень. Например, " примитивный корень третьей степени, а корень четвертой степени ¡1 не является примитивным (поскольку i не является степенью ¡1).

Поскольку Ekn = 1, то последовательность Eki , i = 1; 2; : : : имеет n в периоде. Из этого вытекает, что корень Ek примитивен если и только если в множестве Eki , i = 0; : : : ; n ¡ 1 встречаются все корни из 1.

Следующее предложение характеризует примитивные корни.

20