Следствия

Алгоритм Евклида.

Следствия.

Определения.

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 с остатком и обозначим остаток r₁. Далее разделим g на r₁ c остатком и обозначим остаток r₂. Затем разделим r₁ на r₂ c остатком и обозначим остаток r₃ и т.д. Описанная процедура называется алгоритмом Евклида. Запишем её в следующую таблицу:

f = gq₁ + r₁, ст.r₁ < ст.g,

g = r₁q₂ + r₂, ст.r₂ < ст.r₁,

r₁= r₂q₃ + r₃, ст.r₃ < ст.r₂,

……………………………… Так как ст.g > ст.r₁ > ст.r₂ >…³ -¥,

то процедура закончится за конечное число шагов:

r_k-3= r_k-2q_k-1 + r_k-1, ст.r_k-1 < ст.r_k-2,

r_k-2= r_k-1q_k + r_k, ст.r_k < ст.r_k-1,

r_k-1= r_kq_k+1, то есть r_k+1 = 0.

Лемма. Множество делителей для f и g совпадает с множеством делителей для g и r₁.

Доказательство. Очевидно, если многочлен d | f, d | g, то d | g, d | r₁, так как r₁= f – gq₁. Наоборот, если d | g, d | r₁, то d | f, d | g.

ÿ

1. Множество делителей для f и g совпадает с множеством делителей для r₁ и r₂, с множеством делителей для r₂ и r₃, …, с множеством делителей для r_k-1 и r_k, с множеством делителей для r_k.

2. Множество наибольших общих делителей для f и g совпадает с множеством наибольших общих делителей для r_k, то есть r_k - один из наибольших общих делителей для f и g.

Таким образом, алгоритм Евклида служит для нахождения наибольшего общего делителя двух многочленов.

Обозначим наибольший общий делитель r_k для f и g через D, и выразим его из предпоследней строки алгоритма Евклида: D= r_k= r_k-2 – r_k-1q_k. Затем поднимемся на одну строку вверх, выразим r_k-1 через r_k-3 и r_k-2 и подставим это выражение в нашу формулу для D. Получим D = и₁r_k-3+v₁r_k-2 для некоторых и₁, v₁Î P [x]. Далее поднимемся ещё на одну строку вверх, выразим r_k-2 через r_k-4 и r_k-3 и снова подставим это выражение в нашу формулу для D. Получим D= и₂r_k-4+v₂r_k-3 для некоторых и₂, v₂Î 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+ r₁, ст. r₁< ст.g. Тогда

D = uf + vg = (gq + r₁) f + vg =r₁f + (qf+ v)g = r₁f + v¢g, где v¢= (qf+ v), и ст.(v¢g) £ ст.(r₁f) Þ ст.v¢ < ст.f.

ÿ

Упражнение. Написать алгоритм Евклида для N, сформулировать и доказать для N утверждения, аналогичные лемме, следствиям и утверждениям из 10.4.

10.5. Однозначность разложения на простые множители в P [x] и в N.

Определение. Элемент р кольца K называется простым, если из разложения р = rs, r, s Î K, следует, что или r |1 или s |1. В кольце P [x] простые многочлены называют ещё неприводимыми многочленами.

Определение. Говорят, что в кольце К разложение на простые множители квазиоднозначно, если " а Î K, а ¹ 0, из существования разложений на простые множители

а = р₁р₂…р_k = q₁q₂…q_s (где все р_i, q_j – простые элементы кольца K) следует, что k = s, и, может быть, после перенумерации мы можем получить р _i = q _ic _i "i, где c _i | 1.

Теорема. В кольце P [x] разложение на простые многочлены существует.

Доказательство от противного. Пусть в P [x] разложение

на простые многочлены не существует. Значит, $ fÎ P [x], для которого не существует разложение на простые многочлены. Следовательно, f – не простой (иначе разложение на простые многочлены для f существует и состоит из одного множителя). Если f – не простой, то f = а₁а₂, где а₁, а₂Î P [x], ст.а₁> 0, ст.а₂ > 0, и либо для а₁, либо для а₂ разложение на простые множители не существует. Пусть не существует разложение на простые многочлены для а₁. Очевидно,

ст.f > ст.а₁, и а₁ - не простой Þ а₁ = b₁b₂, где b₁, b₂Î P [x], ст.b₁> 0, ст.b₂ > 0, и либо для b₁, либо для b₂ разложение на простые множители не существует. Пусть не существует для b₁ Þ ст.a₁ > ст.b₁, и b₁ - не простой Þ b₁ = c₁c₂ и т.д. С одной стороны процесс никогда не закончится, а с другой стороны ст.f > ст.а₁> ст.b₁>…, и процесс до бесконечности продолжаться не может. Получили противоречие.

ÿ

Лемма. Пусть h и f - взаимно простые, и h | (fg). Тогда h | g.

Доказательство. Так как h и f - взаимно простые, то hf является их наименьшим общим кратным, а fg - их общее кратное по условию леммы. По теореме из 10.3 (hf) |(fg), то есть h | g.

ÿ

Теорема. В кольце P [x] разложение на простые многочлены квазиоднозначно.

Доказательство. Пусть для некоторого f Î P [x] имеем

разложения f = р₁р₂…р_k = q₁q₂…q_s (где все р_i, q_j – простые многочлены кольца P [x]). Очевидно, р₁| q₁(q₂…q_s), и если р₁ и q₁ – взаимно простые многочлены, то по лемме р₁| (q₂…q_s). Аналогично, если р₁ и q₂ – взаимно простые, то р₁| (q₃…q_s), и т.д. В конце концов мы получим, что существует i такое, что р₁ и q_i – не взаимно простые, то есть q_i = с₁р₁, с₁Î P. Сократив равенство р₁р₂…р_k = q₁q₂…q_s на р₁, получим

р₂…р_k = с₁q₁q₂… …q_s (крышка над q_i означает, что множи-

тель q_i отсутствует). Далее переходим к р₂. Как и ранее, получим, что для р₂ существует q_j такой, что q_j = с₂р₂, с₂Î P. Опять сокращаем равенство на р₂ и переходим к р₃, и т.д. После сокращения на все левые множители р₁, р₂,…, р_k, получим, что k = s и 1 = с₁с₂…с_k.

ÿ

Упражнение. Сформулировать и доказать существование и однозначность разложения на простые множители в N.

Лекция 22.

Дата добавления: 2014-01-04