Лекции по линейной алгебре (стр. 21 )

Очевидно,  fg – общее кратное для  f  и  g, то есть общие

кратные для  f и g существуют, а следовательно, существуют и наименьшие общие кратные.

Теорема. Если М - общее кратное для  f и g, а т - наименьшее общее кратное, то  т | M.

Доказательство. Разделим М на т  с остатком: М=тq+ r,  и ст. r ст. т ⇒  r = M – mq, и так как  f и g  делят правую часть равенства, то  f | r, g |r, то есть r – общее кратное для f и g. Но т – наименьшее общее кратное для  f и g, а  ст. r ст. т ⇒  r = 0 ⇒ т | M.

  Следствие. Если т1  и т2 наименьшие общие кратные для  f и g, то т1|т2  и  т2|т1 ⇒  т2 = aт1, т1 = bт2 ⇒  т2 = abт2 ⇒  т2(1 – ab) = 0 ⇒  1 – ab = 0  ⇒ ab = 1 ⇒ a, b ∈ P.  Следовательно, любые два наименьших общих кратных для  f  и  g

отличаются на ненулевой множитель из  Р.  Наоборот, если т – наименьшее общее кратное для  f и g, то ∀ а ∈ Р, а ≠ 0, ат -  также наименьшее общее кратное для f и g, и значит, {am |а ∈ Р, а ≠ 0} – множество всех наименьших общих кратных для  f  и  g.

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

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.

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

  Пусть 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.

10.6. Производная.