API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Jun 30th, 2016
59
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
HTML 11.73 KB | None | 0 0
raw download clone embed print report
  1. <!-- (C) 2010 Nesterenkov Sergey, BSUIR -->
  2. <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//RU">
  3. <HTML>
  4. <HEAD>
  5. <LINK rel=stylesheet href="../../../Оболочка/css/style.css" type=text/css>
  6. <META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=windows-1251">
  7. <script type="text/javascript"
  8.  src="https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
  9. </script>
  10. <META HTTP-EQUIV="Content-Language" CONTENT="ru">
  11. <title>Теория по теме N26</title>
  12. <base target="_top">
  13. </HEAD><BODY id="main_body">
  14.  
  15. <P class="margined"><FONT SIZE=4><CENTER></CENTER></FONT>
  16.  
  17. <div>
  18. $$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;d(x) = \sum_{i=1}^S u_{i}(x)f_{i}(x).\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;4.3.3 $$
  19. <p class="p_indent">\(\triangleright \) Доказательство проводится методом математической индукции с использованием теоремы 4.3.6 и рекурсивного вычисления НОД многочленов. \(\triangleleft \)</p>
  20. <p class="p_indent"><strong>Определение 4.3.3.</strong> Равенство (4.3.3) называют соотношением Безу для наибольшего общего делителя многочленов.</p>
  21. <p class="p_indent"><strong>Замечание.</strong> Многочлены <i>u</i><sub>1</sub>(<i>x</i>), <i>u</i><sub>2</sub>(<i>x</i>),…, <i>u</i><sub>s</sub>(<i>x</i>) &isin; <i>P</i>[<i>x</i>] в (4.3.3) не являются единственными с таким условием. Так, например, легко видеть, что при <i>s</i> = 2, если <i>d</i>(<i>x</i>) = <i>u</i><sub>1</sub>(<i>x</i>)<i>f</i><sub>1</sub>(<i>x</i>) + <i>u</i><sub>2</sub>(x)<i>f</i><sub>2</sub>(<i>x</i>), то для любого многочлена <i>q</i>(<i>x</i>) &isin; <i>P</i>[<i>x</i>] многочлены <i>u</i><sub>1</sub>(<i>x</i>) + <i>q</i>(<i>x</i>)<i>f</i><sub>2</sub>(<i>x</i>)/<i>d</i>(<i>x</i>) и <i>u</i><sub>2</sub>(<i>x</i>) – <i>q</i>(<i>x</i>)<i>f</i><sub>1</sub>(x)/<i>d</i>(<i>x</i>) из <i>P</i>[<i>x</i>] также являются коэффициентами данного соотношения Безу при <i>f</i>
  22. (<i>x</i>) и <i>f</i><sub>2</sub>(<i>x</i>) соответственно.</p>
  23. <p class="p_indent"><strong>Пример 4.3.2.</strong> Найдем <i>u</i>(<i>x</i>), <i>v</i>(<i>x</i>) &isin; <strong>Q</strong>[<i>x</i>] в соотношении Безу для НОД многочленов <i>f</i>(<i>x</i>) и <i>g</i>(<i>x</i>) из примера 4.3.1, равного <i>d</i>(<i>x</i>) = <i>x</i> + 3.</p>
  24. $$d(x) = 1/9g(x) - 1/9 \widetilde{r_{1}}(x)(3x - 5) = 1/9g(x) - 1/5(3x - 5)(-f(x)) + g(x)(1/3x - 1/9)) = (3/5x - 1)f(x) + (-1/5x^{2} + 2/5x)g(x) $$
  25. <p>Таким образом, \(u(x) = 3/5x - 1, v(x) = -1/5x^{2} + 2/5x. \)</p>
  26. <p class="p_indent">Согласно приведенному выше замечанию для всех <i>q</i>(<i>x</i>) &isin; <strong>Q</strong>[<i>x</i>] многочлены <i>u</i><sub><i>q</i></sub>(<i>x</i>) = <i>u</i>(<i>x</i>) + <i>q</i>(<i>x</i>)<i>g</i>(<i>x</i>)/<i>d</i>(<i>x</i>) и <i>v<sub>q</sub></i>(<i>x</i>) = <i>v</i>(<i>x</i>) – <i>q</i>(<i>x</i>)<i>f</i>(<i>x</i>)/<i>d</i>(<i>x</i>) также являются коэффициентами данного соотношения Безу при <i>f</i>(<i>x</i>) и <i>g</i>(<i>x</i>) соответственно. Например, при <i>q</i>(<i>x</i>) = 1 получаем <i>u</i><sub>1</sub>(<i>x</i>) = <i>u</i>(<i>x</i>) + <i>g</i>(<i>x</i>)/<i>d</i>(<i>x</i>) = 3<i>x</i><sup>2</sup> + 8/5<i>x</i> – 2 и <i>v</i><sub>1</sub>(<i>x</i>) = v(<i>x</i>) – <i>f</i>(<i>x</i>)/<i>d</i>(<i>x</i>) = – <i>x</i><sup>3</sup> – 1/5<i>x</i><sup>2</sup> + 7/5<i>x</i> + 1.&bull;</p>
  27. <p class="p_indent"><strong>Определение 4.3.4.</strong> <i>Общим кратным</i> (<i>ОК</i>) ненулевых многочленов <i>f</i><sub>1</sub>(<i>x</i>), <i>f</i><sub>2</sub>(<i>x</i>),…, <i>f</i><sub>s</sub>(<i>x</i>)) &isin; <i>P</i>[<i>x</i>], где <i>s</i> &isin; <strong>N</strong><sub>&ge;2</sub>, называется многочлен <i>m</i>(<i>x</i>) &isin; <i>P</i>[<i>x</i>], такой, что <i>m</i>(<i>x</i>): <i>f<sub>i</sub></i>(<i>x</i>), <i>i</i> = 1, <i>s</i> .<i> Наименьшим общим кратным</i> (<i>НОК</i>) ненулевых многочленов <i>f</i><sub>1</sub>(<i>x</i>),  <i>f</i><sub>2</sub>(<i>x</i>),…,<i>f<sub>s</sub></i>(<i>x</i>) называется такое их нормированное общее кратное (со старшим коэффициентом 1), на которое делится любое другое их общее кратное. Таким образом, нормированность гарантирует однозначность НОК. Его обозначают НОК(<i>f</i><sub>1</sub>(<i>x</i>), <i>f</i><sub>2</sub>(<i>x</i>),…, <i>f</i><sub>s</sub>(<i>x</i>)) или, если это не вызывает разночтений, [<i>f</i><sub>1</sub>(<i>x</i>), <i>f</i><sub>2</sub>(<i>x</i>),…, <i>f</i><sub>s</sub>(<i>x</i>)].</p>
  28. <p class="p_indent">Очевидно, что если <i>g</i>(<i>x</i>)|<i>f</i>(<i>x</i>), то при <i>f</i>(<i>x</i>) &ne; 0 имеем [<i>g</i>(<i>x</i>), <i>f</i>(<i>x</i>)] = <i>a<sub>n</sub></i><sup>–1</sup><i>f</i>(<i>x</i>), где <i>a<sub>n</sub></i> – старший коэффициент <i>f</i>(<i>x</i>), deg <i>f</i> = <i>n</i>.</p>
  29. <p class="p_indent">НОК многочленов вычисляется рекурсивно для любого <i>s</i> &ge; 3:</p>
  30. $$[f_{1}(x), f_{2}(x),…,f_{s}(x)] =  \left[[f_{1}(x), f_{2}(x),…, f_{s – 1}(x)], f_{s}(x)\right]. $$
  31. <p class="p_indent"><strong>Определение 4.3.5.</strong> Если (<i>f</i><sub>1</sub>(<i>x</i>), <i>f</i><sub>2</sub>(<i>x</i>),…, <i>f</i><sub>s</sub>(<i>x</i>)) = 1, где <i>s</i> &ge; 2, то многочлены <i>f</i><sub>1</sub>(<i>x</i>), <i>f</i><sub>2</sub>(<i>x</i>),…, <i>f</i><sub>s</sub>(<i>x</i>) называются <i>взаимно простыми</i>.</p>
  32. <p class="p_indent"><strong>Теорема 4.3.7</strong> (<strong>критерий взаимной простоты многочленов</strong>). Многочлены <i>f</i><sub>1</sub>(<i>x</i>), <i>f</i><sub>2</sub>(<i>x</i>),…, <i>f</i><sub>s</sub>(<i>x</i>), &isin; <i>P</i>[<i>x</i>], где <i>s</i> &ge; 2, взаимно просты тогда и только тогда, когда найдутся такие многочлены <i>u</i><sub>1</sub>(<i>x</i>), <i>u</i><sub>2</sub>(<i>x</i>),…, <i>u</i><sub>s</sub>(<i>x</i>) &isin; <i>P</i>[<i>x</i>], что</p>
  33. $$d(x) = \sum_{i=1}^S u_{i}(x)f_{i}(x) = 1 $$
  34. <p class="p_indent">\(\triangleright \) Необходимость. Если (<i>f</i><sub>1</sub>(<i>x</i>), <i>f</i><sub>2</sub>(<i>x</i>),…, <i>f</i><sub>s</sub>(<i>x</i>)) = 1, то по следствию из теоремы 4.3.6 существуют многочлены <i>u</i><sub>1</sub>(<i>x</i>), <i>u</i><sub>2</sub>(<i>x</i>),…, <i>u</i><sub>s</sub>(<i>x</i>) &isin; <i>P</i>[<i>x</i>], такие, что </p>
  35. $$d(x) = \sum_{i=1}^S u_{i}(x)f_{i}(x) = 1 $$
  36. <p class="p_indent">Достаточность. Если данное соотношение справедливо и <i>d</i>(<i>x</i>) = (<i>f</i><sub>1</sub>(<i>x</i>), <i>f</i><sub>2</sub>(<i>x</i>),…, <i>f</i><sub>s</sub>(<i>x</i>)), то по свойству 5 делимости многочленов <i>d</i>(<i>x</i>) | 1, следовательно, deg <i>d</i> = 0. Так как старший коэффициент <i>d</i>(<i>x</i>) равен 1, то <i>d</i>(<i>x</i>) = 1, что означает взаимную простоту многочленов <i>f</i><sub>1</sub>(<i>x</i>)), <i>f</i><sub>2</sub>(<i>x</i>),…, <i>f</i><sub>s</sub>(<i>x</i>) по определению.\(\triangleleft \) </p>
  37. <p class="p_indent">Из этого критерия вытекает ряд важных следствий как свойств взаимно простых многочленов.</p>
  38. <p class="p_indent"><strong>Следствие 1.</strong> Если произведение многочленов <i>f</i>(<i>x</i>) и <i>g</i>(<i>x</i>) делится на многочлен <i>h</i>(<i>x</i>) и (<i>f</i>(<i>x</i>), <i>h</i>(<i>x</i>)) = 1, то <i>g</i>(<i>x</i>) делится на <i>h</i>(<i>х</i>).</p>
  39. <p class="p_indent">\(\triangleright \) Согласно теореме 4.3.7 найдутся <i>u</i>(<i>x</i>), <i>v</i>(<i>x</i>) &isin; <i>P</i>[<i>x</i>], такие, что <i>u</i>(<i>x</i>)<i>f</i>(<i>x</i>) + <i>v</i>(<i>x</i>)<i>h</i>(<i>x</i>) = 1. Умножим на <i>g</i>(<i>x</i>) обе части данного равенства. Получим <i>u</i>(<i>x</i>)<i>f</i>(<i>x</i>)<i>g</i>(<i>x</i>) + <i>v</i>(<i>x</i>) )<i>g</i>(<i>x</i>) = <i>g</i>(<i>x</i>), откуда имеем</p>
  40. $$(u(x)q(x) + v(x)g(x)) ) = g(x),$$
  41. <p>поскольку &exist;<i>q</i>(<i>x</i>) &isin; <i>P</i>[<i>x</i>] с условием <i>f</i>(<i>x</i>)<i>g</i>(<i>x</i>) = <i>q</i>(<i>x</i>)<i>h</i>(<i>x</i>). Значит,  <i>h</i>(<i>x</i>)|<i>g</i>(<i>x</i>).\(\triangleleft \) </p>
  42. <p class="p_indent"><strong>Следствие 2.</strong> Многочлен <i>f</i>(<i>x</i>) взаимно прост с каждым из многочленов <i>g</i>(<i>х</i>) и <i>h</i>(<i>х</i>) тогда и только тогда, когда он взаимно прост с их произведением.</p>
  43. <p class="p_indent">\(\triangleright \) Необходимость. Так как (<i>f</i>(<i>x</i>), <i>g</i>(<i>х</i>)) = 1 и (<i>f</i>(<i>x</i>), <i>h</i>(<i>х</i>)) = 1, то согласно теореме 4.3.7 найдутся <i>u</i><sub>1</sub>(<i>x</i>),<i>v</i><sub>1</sub>(<i>x</i>), <i>u</i><sub>2</sub>(<i>x</i>), <i>v</i><sub>2</sub>(<i>x</i>) &isin; <i>P</i>[<i>x</i>], такие, что выполняются равенства <i>u</i><sub>1</sub>(<i>x</i>)<i>f</i>(<i>x</i>) + <i>v</i><sub>1</sub>(<i>x</i>)<i>f</i>(<i>x</i>) и <i>u</i><sub>2</sub>(<i>x</i>)<i>f</i>(<i>x</i>) + <i>v</i><sub>2</sub>(<i>x</i>)<i>f</i>(<i>x</i>) = 1. Тогда, перемножая почленно данные равенства, получим</p>
  44. $$u_{1}(x)u_{2}(x)f(x) + u_{1}(x)v_{2}(x)h(x) + v_{1}(x)u_{2}(x)f(x) + v_{1}(x)v_{2}(x)f(x)g(x) = 1$$
  45. <p class="p_indent">т. е. выполняется критерий взаимной простоты для многочленов <i>f</i>(<i>x</i>) и <i>g</i>(<i>х</i>)<i>h</i>(<i>х</i>).</p>
  46. <p class="p_indent">Достаточность. Пусть (<i>f</i>(<i>x</i>), <i>g</i>(<i>x</i>)<i>h</i>(<i>x</i>)) = 1. Если предположить, что (<i>f</i>(<i>x</i>), <i>g</i>(<i>x</i>)) = <i>d</i><sub>1</sub>(<i>x</i>) &ne; 1 или (<i>f</i>(<i>x</i>), <i>h</i>(<i>x</i>)) = <i>d</i><sub>2</sub>(<i>x</i>) &ne; 1, то согласно свойству 3 делимости многочленов и определению НОД получим, что <i>d</i><sub>1</sub>(<i>x</i>) | (<i>f</i>(<i>x</i>), <i>g</i>(<i>x</i>)<i>h</i>(<i>x</i>)) либо <i>d</i><sub>2</sub>(<i>x</i>) | (<i>f</i>(<i>x</i>), <i>g</i>(<i>x</i>)<i>h</i>(<i>x</i>)). Это противоречит тому, что (<i>f</i>(<i>x</i>), <i>g</i>(<i>x</i>)<i>h</i>(<i>x</i>)) = 1. Значит, (<i>f</i>(<i>x</i>), <i>g</i>(<i>x</i>)) = 1 и (<i>f</i>(<i>x</i>), <i>h</i>(<i>x</i>)) = 1. \(\triangleleft \)</p>
  47.  
  48.  
  49.  
  50.  
  51. </div>
  52.  
  53. </BODY></HTML>
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!