Следствия.
Алгоритм Евклида.
Следствия.
Определения.
1. Многочлен D называется наибольшим общим делителем многочленов f и g , если D имеет наибольшую степень среди всех общих делителей f и g.
2. Многочлены f и g называются взаимно простыми, если 1 является их наибольшим общим делителем.
Теорема. 1) Если т – наименьшее общее кратное для f и g, то D =(fg)/m – их наибольший общий делитель. 2) Если d - общий делитель многочленов f и g, а D¢ – их наибольший общий делитель, то d |D¢.
Доказательство. Очевидно, D | f, так как f / D = m /g = =hÎP[x]. Аналогично, D | g. Следовательно, D - общий делитель для f и g. Если d – произвольный общий делитель для f и g , то M = (fg)/d – общее кратное для f и g , так как М / f = = g / d ÎP[x] и аналогично М / g ÎP[x]. По предыдущей теореме т | M, то есть М = qm Þ (fg)/d = q(fg) / D Þ D =qd Þ d |D Þ ст.D ³ ст.d Þ D – наибольший общий делитель для f и g.
Теперь если D¢ – произвольный наибольший общий делитель многочленов f и g, то ст.D¢ = ст.D, и D¢|D Þ D = aD¢, а Î РÞ d |D¢.
ÿ
1. Если D – наибольший общий делитель многочленов f
и g, то {aD | a Î P, a ¹ 0} – множество всех наибольших общих делителей многочленов f и g .
2. Если f и g – взаимно простые многочлены, то fg является их наименьшим общим кратным.
Определение.Пусть т, п Î N. Разделить т на п с остатком – это найти такие q и r, что m = nq + r, 0 £ r < n .
Замечание. Для множества N натуральных чисел можно дать определения, аналогичные определениям из 10.3 и доказать теоремы, аналогичные теоремам из 10.2, 10.3.
Упражнение. Сформулировать и доказать теоремы, аналогичные теоремам из 10.2, 10.3, для N.
Пусть f, g Î P[x], g ¹ 0. Разделим f на g с остатком и обозначим остаток r1. Далее разделим g на r1 c остатком и обозначим остаток r2. Затем разделим r1 на r2 c остатком и обозначим остаток r3 и т.д. Описанная процедура называется алгоритмом Евклида. Запишем её в следующую таблицу:
f = gq1 + r1, ст.r1 < ст.g,
g = r1q2 + r2, ст.r2 < ст.r1,
r1= r2q3 + r3, ст.r3 < ст.r2,
……………………………… Так как ст.g > ст.r1 > ст.r2 >…³ -¥,
то процедура закончится за конечное число шагов:
rk-3= rk-2qk-1 + rk-1, ст.rk-1 < ст.rk-2,
rk-2= rk-1qk + rk, ст.rk < ст.rk-1,
rk-1= rkqk+1, то есть rk+1 = 0.
Лемма. Множество делителей для f и g совпадает с множеством делителей для g и r1.
Доказательство.Очевидно, если многочлен d | f , d | g , то d | g , d | r1, так как r1= f – gq1. Наоборот, если d | g , d | r1, то d | f , d | g.
ÿ
1. Множество делителей для f и g совпадает с множеством делителей для r1 и r2 , с множеством делителей для r2 и r3 , …, с множеством делителей для rk-1 и rk , с множеством делителей для rk .
2. Множество наибольших общих делителей для f и g совпадает с множеством наибольших общих делителей для rk, то есть rk - один из наибольших общих делителей для f и g.
Таким образом, алгоритм Евклида служит для нахождения наибольшего общего делителя двух многочленов.
Обозначим наибольший общий делитель rk для f и g через D, и выразим его из предпоследней строки алгоритма Евклида: D= rk= rk-2 – rk-1qk. Затем поднимемся на одну строку вверх, выразим rk-1 через rk-3 и rk-2 и подставим это выражение в нашу формулу для D. Получим D = и1rk-3+v1rk-2 для некоторых и1, v1Î P[x]. Далее поднимемся ещё на одну строку вверх, выразим rk-2 через rk-4 и rk-3 и снова подставим это выражение в нашу формулу для D. Получим D= и2rk-4+v2rk-3 для некоторых и2, v2Î P[x]. И так далее. В конце концов получим выражение D через f и g : D= uf + vg, где u, vÎ P[x].
Таким образом, в качестве следствия из алгоритма Евклида доказано следующее
Утверждение 1.Если D - наибольший общий делитель для f, g Î P[x], то $ u, vÎ P[x] такие, что D = uf + vg .
Утверждение 2. В выражении D = uf + vg можно выбрать u, v так, что ст.и < ст.g, ст.v < ст.f.
Доказательство. Разделим и на g c остатком: и= gq+ r1, ст. r1< ст.g. Тогда
D = uf + vg = (gq + r1) f + vg =r1f + (qf+ v)g = r1f + v¢g , где v¢= (qf+ v), и ст.(v¢g) £ ст.(r1f) Þ ст.v¢ < ст.f.
ÿ
Упражнение. Написать алгоритм Евклида для N, сформулировать и доказать для N утверждения, аналогичные лемме, следствиям и утверждениям из 10.4.
10.5. Однозначность разложения на простые множители в P[x] и в N.
Определение.Элемент р кольца K называется простым, если из разложения р = rs, r, s Î K, следует, что или r |1 или s |1. В кольце P[x] простые многочлены называют ещё неприводимыми многочленами.
Определение.Говорят, что в кольце К разложение на простые множители квазиоднозначно, если " а Î K, а ¹ 0, из существования разложений на простые множители
а = р1р2…рk = q1q2…qs (где все рi , qj – простые элементы кольца K) следует, что k = s, и, может быть, после перенумерации мы можем получить р i = q ic i "i, где c i | 1.
Теорема.В кольце P[x] разложение на простые многочлены существует.
Доказательствоот противного. Пусть в P[x] разложение
на простые многочлены не существует. Значит, $ fÎ P[x], для которого не существует разложение на простые многочлены. Следовательно, f – не простой (иначе разложение на простые многочлены для f существует и состоит из одного множителя). Если f – не простой, то f = а1а2 , где а1, а2Î P[x], ст.а1> 0, ст.а2 > 0, и либо для а1, либо для а2 разложение на простые множители не существует. Пусть не существует разложение на простые многочлены для а1. Очевидно,
ст.f > ст.а1, и а1 - не простой Þ а1 = b1b2 , где b1, b2Î P[x], ст.b1> 0, ст.b2 > 0, и либо для b1, либо для b2 разложение на простые множители не существует. Пусть не существует для b1 Þ ст.a1 > ст.b1, и b1 - не простой Þ b1 = c1c2 и т.д. С одной стороны процесс никогда не закончится, а с другой стороны ст.f > ст.а1> ст.b1>…, и процесс до бесконечности продолжаться не может. Получили противоречие.
ÿ
Лемма. Пусть h и f - взаимно простые, и h | (fg). Тогда h | g.
Доказательство.Так как h и f - взаимно простые, то hf является их наименьшим общим кратным, а fg - их общее кратное по условию леммы. По теореме из 10.3 (hf) |(fg), то есть h | g.
ÿ
Теорема.В кольце P[x] разложение на простые многочлены квазиоднозначно.
Доказательство.Пусть для некоторого f Î P[x] имеем
разложения f = р1р2…рk = q1q2…qs (где все рi , qj – простые многочлены кольца P[x]). Очевидно, р1| q1(q2…qs), и если р1 и q1 – взаимно простые многочлены, то по лемме р1| (q2…qs). Аналогично, если р1 и q2 – взаимно простые, то р1| (q3…qs), и т.д. В конце концов мы получим, что существует i такое, что р1 и qi – не взаимно простые, то есть qi = с1р1, с1Î P. Сократив равенство р1р2…рk = q1q2…qs на р1, получим
р2…рk = с1q1q2…
…qs (крышка над qi означает, что множи-
тель qi отсутствует). Далее переходим к р2. Как и ранее, получим, что для р2 существует qj такой, что qj = с2р2, с2Î P. Опять сокращаем равенство на р2 и переходим к р3, и т.д. После сокращения на все левые множители р1, р2,…, рk, получим, что k = s и 1 = с1с2…сk .
ÿ
Упражнение. Сформулировать и доказать существование и однозначность разложения на простые множители в N.
Лекция 22.