1610841785-f468a61572dab6722e8deb8e3ec644ad (824277), страница 7

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 7)

Еслиg | f , то, очевидно, (f, g) = g (в частности, (g, 0) = g). Если 0 6= g - f и deg g 6 deg f , то разделим f на gс остатком: f = gq1 +r1 , deg r1 < deg g, при этом r1 6= 0. У пар {f, g} и {g, r1 } одинаковое множество общихделителей: d | g, gq1 + r1 ⇔ d | g, r1 . Повторим то же рассуждение для пары {g, r1 } и так до тех пор, покаодин многочлен в паре не разделится на другой без остатка (рано или поздно это обязательно произойдёт,т. е. процесс последовательного деления с остатком на некотором шаге завершится, иначе мы получили быбесконечную убывающую последовательность целых неотрицательных чисел deg g > deg r1 > deg r2 > .

. .,что невозможно):f = gq1 + r1 ,deg r1 < deg g,g = r1 q2 + r2 ,deg r2 < deg r1 ,r1 = r2 q3 + r3 ,deg r3 < deg r2 ,......rn−2 = rn−1 qn + rn ,(1)deg rn < deg rn−1 ,rn−1 = rn qn+1 .Теорема. Последний ненулевой остаток rn в (1) равен (f, g), и он выражается линейнойкомбинацией f и g, т. е. для некоторых u, v ∈ K[x] выполнено соотношение Безу5 :(f, g) = f u + gv.(2)C Двигаясь по цепочке (1) снизу вверх, видим, что rn делит rn−1 , rn−2 , . . ., r1 , g, f и, крометого, rn выражается через f и g:rn = rn−2 − rn−1 qn = rn−2 − (rn−3 − rn−2 qn−1 )qn = . .

. = f u + gv.Но всякая линейная комбинация f и g, очевидно, кратна любому общему делителю f и g. B5В честь Этьена Безу. Впервые этот факт был опубликован для взаимно простых целых чисел французскимматематиком Мезириаком в 1624 году.Описанная процедура линейного выражения НОД называется обратным ходом алгоритмаЕвклида. Так, для рассмотренного выше примера имеем:(f, g) = 31(x2 − x + 1) = (f − xg)(4x + 1) − 16g = (4x + 1)f − (x + 16)gОтметим, что на практике многочлены u и v бывает удобнее искать методом неопределённыхкоэффициентов. При этом ограничения на степени u и v даёт следующая задача.1.

Пусть K — поле, f, g ∈ K[x], (f, g) = 1, deg f, deg g > 0. Докажите, что существуют такиемногочлены u, v ∈ K[x], что uf + vg = 1 и deg u < deg g, deg v < deg f .Пример. Найдём (f, g) и соотношение Безу для f (x) = x3 − 2 и g(x) = x2 + x + 3.I способ. Действуем по алгоритму Евклиду:x3 − 2 = (x2 + x + 3)(x − 1) − 2x + 1x2 + x + 3 = (2x − 1) 12 x + 34 + 154154= g(x) − (g(x)(x− 1) − f (x)) 12 x + 34 == f (x) 12 x + 43 + g(x) − 12 x2 − 14 x + 47 .II способ.

Очевидно, многочлены f и g взаимно просты. По задаче 1 имеем:(ax + b)(x3 − 2) − (ax2 + cx + d)(x2 + x + 3) = 1для некоторых a, b, c, d ∈ Q. Приравняв коэффициенты при 1, x, x2 , x3 , получим2c = 15−2b − 3d = 1a = 2ca = 1 −2a − 3c − d = 0 b = a + c = 3c15⇐⇒11 ⇐⇒ 1b= 5−3a − c − d = 0d = − 3 (2b + 1) = −2c − 317.c = −3a − d = −4c + 3d = − 15b−a−c=0Ответ: 15 = (2x + 3)f (x) − (2x2 + x − 7)g(x).2. Для m, n ∈ N найдите: а) (2m − 1, 2n − 1) в Z; б) (xm − 1, xn − 1) в Q[x].3. Важная теоретическая задача. Пусть многочлен f ∈ Q[x] неприводим над Q. Докажите,что он не имеет кратных комплексных корней.4. Применение алгоритма Евклида. Избавьтесь от иррациональности в знаменателе:15−18√√; б) √;а) √3334− 2−24+ 32+3Простейшие примеры:√12−1=√2 + 1,в)α, если α3 − α + 1 = 0;α+11√32+1=√3√4− 3 2+1.3г)1.cos 2π7Но для решения задачи 4 уже недостаточно банального умножения на сопряжённое.

Впрочем,√ в пунктеа) ещё можно схитрить, разложив знаменатель на множители как квадратный трёхчлен от 3 2:√ √√√−18(2 + 1)(2 − 23 )3333√√√√==4−2+14+22+4,334− 32−22+1 32−2но в пункте б) аналогичное разложение знаменателя x2 +x+3|x= √32 приведёт к новым иррациональностям,к тому же мнимым. Продемонстрируем на этом примере, как действовать, если в √знаменателе стоит3многочлен от одной иррациональности, скажем, от радикала. В нашем случае это α = 2. Быстрый успех1с дробью α+1объяснить легко: без труда подбирается многочлен от α, а именно, α2 − α + 1, умножениекоторого на знаменатель α + 1 даёт константу ввиду соотношения α3 − 2 = 0. Как подобрать такоймножитель для знаменателя α2 + α + 3? Нужно найти такой многочлен u(x) ∈ Q[x], чтоu(x)(x2 + x + 3) + v(x)(x3 − 2) = 1(3)для некоторого многочлена v(x) ∈ Q[x].

Тогда при подстановке x = α получим требуемое:α21= u(α).+α+3Но равенство (3) есть не что иное как соотношение Безу — линейное представление НОД! Многочлены uи v ищутся по алгоритму Евклида или методом неопределённых коэффициентов:(2x2 + x − 7)(x2 + x + 3) − (2x + 3)(x3 − 2) = −15 =⇒12α2 + α − 7=−.α2 + α + 315Корни из единицы и круговые многочленыНапомним, что корни степени n из единицы образуют группу√ n1 = εkn k ∈ Z = hεn i, где εn := cos 2π+ i sin 2π— один из её порождающих,nnт. е. один из первообразных корней n-й степени из единицы.√1. Теорема. εjn — первообразный корень n-й степени из единицы, т.

е. n 1 = hεjn i, ⇔ (j, n) = 1.C ⇒ Если (j, n) = d > 1, то 1 — противоречие.(n−1)j⇐ Пусть (j, n) = 1. Покажем, что числа 1, εjn , ε2jразличны. 2 Bn , . . . , εn√√√mn(m,n)2. Докажем, что 1 ∩ 1 =1.√ √√ √√C I способ. Ясно, что (m,n) 1 ⊆ m 1∩ n 1. Обратно, пусть α ∈ m 1∩ n 1, т. е. αm = αn = 1. По алгоритмуЕвклида (m, n) = um + vn для некоторых u, v ∈ Z. Отсюда α(m,n) = αum+vn = (αm )u (αn )v = 1.II способ.

Докажем индукцией по m + n эквивалентное утверждение: (xm − 1, xn − 1) = x(m,n) − 1. Еслиm + n = 2, т. е. m = n = 1, то это очевидно. Шаг индукции при m > n:(xm − 1, xn − 1) = (xm − xn , xn − 1) = (xm−n − 1, xn − 1) = x(m−n,n) − 1 = x(m,n) − 1. BQЗапишем разложение xn − 1 = nj=1 (x − εjn ). Перемножив скобки только с первообразными корнями, получим т. н. круговой многочлен (многочлен деления круга, циклотомический6 полином):YΦn (x) :=(x − εjn ).16j6n,(j,n)=1В частности, Φ1 (x) = x − 1 и x − 1 - Φn (x) при n > 1.

Ясно, что deg Φn = ϕ(n).Вот несколько примеров; на картинках сплошными кружочками отмечены первообразные корни соответствующей степени из единицы, а пустыми — остальные.Φ1 (x) = x − 1Φ6 (x) ==x3 +1x+1Φ2 (x) =x6 −1(x3 −1)(x+1)=x2 −1x−1=x+1Φ8 (x) == x2 − x + 1Φ3 (x) =x8 −1x4 −1x3 −1x−1= x4 + 1= x2 + x + 1Φ12 (x) ==x6 +1x2 +1Φ4 (x) =x12 −1(x6 −1)(x2 +1)x4 −1x2 −1= x2 + 1== x4 − x2 + 13. Нарисуйте аналогичные картинки и вычислите многочлены Φn (x) для n = 5, 9, 10.4.

Поясните, что для простых p верны равенстваΦp (x) =xp − 1= xp−1 + . . . + x + 1,x−1и обобщите их на степени простых, вычислив Φpk (x).6Циклотомия — деление круга.5. Докажите, что а) каждый корень из единицы степени n является первообразным ровнодля одной степени d, причём d | n; б) (Φm , Φn ) = 1 при m 6= n.6. Свойства круговых многочленов и формулы для их вычисления во многом аналогичны свойствам функции Эйлера. В следующей таблице эти свойства сгруппированы в пары:сравнив степени многочленов в тождестве из левого столбца, получаем соответствующее ему тождество из правого столбца.QP(Φ1) xn − 1 = Φd (x)(ϕ1) n = ϕ(d)d|nd|np Φn (x ), если простое p | n,(Φ2) Φpn (x) = Φn (xp ), если простое p - nΦn (x)(ϕ2) ϕ(pn) =(Φ3) Φn (x) = Φp1 ...ps (xn/p1 ...ps ),(ϕ3) ϕ(n) =(pϕ(n),если простое p | n,(p − 1)ϕ(n), если простое p - nnϕ(p1p1 ...ps.

. . ps )где p1 , . . . , ps — все простые делители n(Φ4) Φ2n (x) = Φn (−x) для нечётных n > 1Q(Φ5) Φn (x) = (xd − 1)µ(n/d)d|n(ϕ4) ϕ(2n) = ϕ(n) для нечётных n > 1P(ϕ5) ϕ(n) = dµ ndd|nТождество (Φ1) вытекает из задачи 5: согласно пункту а) все корни двучлена xn − 1 являютсякорнями правой части и, наоборот, если d | n, то Φd (x) | xd − 1 | xn − 1, причём согласно пунктуб) корни многочленов Φd разные при разных d (кратных корней справа, как и слева, нет). Значит, левая и правая части тождества (Φ1) делят друг друга. Остаётся заметить, что их старшиекоэффициенты равны 1, и поэтому эти многочлены равны.7. Доказательство остальных тождеств — задача для читателя.Тождество (Φ1) позволяет вычислять многочлены Φn рекуррентно: если известны все Φm приm < n, то Φn можно найти по формулеΦn (x) =xn − 1Q,Φd (x)d|n, d<nиз которой по индукции также следует, что Φn (x) ∈ Z[x]. Приведём примеры:(Φ1)• Φ15 (x) =(Φ2)x15 − 1x10 + x5 + 1x15 − 1= 5== x8 −x7 +x5 −x4 +x3 −x+1;Φ1 (x)Φ3 (x)Φ5 (x)(x − 1)(x2 + x + 1)x2 + x + 1(Φ4 )• Φ20 (x) = Φ10 (x2 ) = Φ5 (−x2 ) = x8 − x6 + x4 − x2 + 1;(Φ3)• Φ54 (x) = Φ6 (x9 ) = x18 − x9 + 1.Интересный факт: коэффициенты круговых многочленов из первой сотни равны 0, ±1.

Впервые этонарушается для многочлена Φ105 .8. Найдите Φn (x) для n = 21, 48, 100, 200.9. При каждом n ∈ N вычислите а) Φn (0); б) Φn (1).Теорема. Круговые многочлены неприводимы над Q. (Доказательство будет позднее.)Разложение многочленов на неприводимые множителиМногочлен f над полем K называется приводимым (над K), если f = gh для некоторыхмногочленов g, h ∈ K[x] положительной степени. Остальные многочлены положительной степенив K[x] называются неприводимыми. (Конcтанты не считаются неприводимыми многочленами7 .)• Все многочлены первой степени неприводимы.• Многочлен степени > 1, имеющий корень, приводим (следует из теоремы Безу).• Приводимость многочлена второй или третьей степени равносильна наличию у него корня.(Для многочленов степени > 3 утверждение неверно, например, многочлен (x2 + 1)2 приводим, но не имеет корней в R.)• Неприводимый многочлен может стать приводимым при расширении поля. Например, многочлен x2 − 2 приводим над R, но неприводим над Q.Неприводимые многочлены играют ту же роль «мультипликативных строительных блоков»,что и простые числа: в кольце K[x] над полем имеет место аналог основной теоремы арифметики.Теорема 1.

Всякий многочлен положительной степени над полем раскладывается на неприводимые множители, и притом однозначно с точностью до перестановки и ассоциированностимножителей.Многим кажется, что теорема (как и её числовой аналог) очевидна и доказывать тут нечего8 .

Характеристики

Список файлов семинаров