17.2: Алгоритм поділу

Нагадаємо, що алгоритм ділення для цілих чисел (Теорема 2.9) говорить, що якщо\(a\) і\(b\) є цілими числами з\(b \gt 0\text{,}\) то існують унікальні цілі числа\(q\) і\(r\) такі, що\(a = bq + r\text{,}\) де\(0 \leq r \lt b\text{.}\) Алгоритм, за яким\(q\) і\(r\) знаходять, просто довгий поділ. Подібна теорема існує і для многочленів. Алгоритм поділу для поліномів має кілька важливих наслідків. Оскільки його доказ дуже схожий на відповідний доказ для цілих чисел, варто переглянути теорему 2.9 на цьому етапі.

Теорема\(17.6\). Division Algorithm

\(f(x)\)\(g(x)\)Дозволяти і бути многочленами в\(F[x]\text{,}\) де\(F\) є поле і\(g(x)\) є ненульовим многочленом. Тоді існують унікальні многочлени\(q(x), r(x) \in F[x]\) такі, що

\[ f(x) = g(x) q(x) + r(x)\text{,} \nonumber \]

де\(\deg r(x) \lt \deg g(x)\) або\(r(x)\) - нульовий многочлен.

Доказ

Ми спочатку розглянемо існування\(q(x)\) і\(r(x)\text{.}\) Якщо\(f(x)\) - нульовий многочлен, то

\[ 0 = 0 \cdot g(x) + 0; \nonumber \]

отже, обидва\(q\) і\(r\) повинні бути також нульовим многочленом. Тепер припустимо, що\(f(x)\) це не нульовий многочлен і що\(\deg f(x) = n\) і\(\deg g(x) = m\text{.}\) Якщо\(m \gt n\text{,}\) тоді ми можемо дозволити\(q(x) = 0\) і\(r(x) = f(x)\text{.}\) Отже, ми можемо припустити, що\(m \leq n\) і продовжити індукцію на\(n\text{.}\) Якщо

\ почати {вирівнювати*} f (x) & = a_n x^n + a_ {n-1} x^ {n - 1} +\ cdots + a_1 x + a_0\\ g (x) & = b_m x^m + b_ {m-1} x^ {m - 1} +\ cdots + b_1 x + b_0\ end {align*}

многочлен

\[ f'(x) = f(x) - \frac{a_n}{b_m} x^{n - m} g(x) \nonumber \]

має ступінь менше\(n\) або дорівнює нульовому многочлену. За індукцією існують\(q'(x)\) многочлени і\(r(x)\) такі, що

\[ f'(x) = q'(x) g(x) + r(x)\text{,} \nonumber \]

де\(r(x) = 0\) або ступінь\(r(x)\) менше, ніж ступінь\(g(x)\text{.}\) Тепер нехай

\[ q(x) = q'(x) + \frac{a_n}{b_m} x^{n - m}\text{.} \nonumber \]

Тоді

\[ f(x) = g(x) q(x) + r(x)\text{,} \nonumber \]

з\(r(x)\) нульовим многочленом або\(\deg r(x) \lt \deg g(x)\text{.}\)

Щоб показати, що\(q(x)\) і\(r(x)\) є унікальними, припустимо, що існують два інших поліноми\(q_1(x)\) і\(r_1(x)\) такі, що\(f(x) = g(x) q_1(x) + r_1(x)\) з\(\deg r_1(x) \lt \deg g(x)\) або\(r_1(x) = 0\text{,}\) так що

\[ f(x) = g(x) q(x) + r(x) = g(x) q_1(x) + r_1(x)\text{,} \nonumber \]

і

\[ g(x) [q(x) - q_1(x) ] = r_1(x) - r(x)\text{.} \nonumber \]

Якщо\(q(x) - q_1(x)\) не нульовий многочлен, то

\[ \deg( g(x) [q(x) - q_1(x) ] )= \deg( r_1(x) - r(x) ) \geq \deg g(x)\text{.} \nonumber \]

Однак ступені обох\(r(x)\) і\(r_1(x)\) строго менше, ніж ступінь\(g(x)\text{;}\) тому,\(r(x) = r_1(x)\) і\(q(x) = q_1(x)\text{.}\)

Приклад\(17.7\)

Алгоритм поділу просто формалізує довгий ділення поліномів, завдання, з яким ми знайомі ще з середньої школи.

Рішення

Наприклад, припустимо, що ми ділимо\(x^3 - x^2 + 2 x - 3\) на\(x - 2\text{.}\)

			\(x^2\)	\(+\)	\(x\)	\(+\)	\(4\)
\(x\)	\(-\)	\(2\)	\(x^3\)	\(-\)	\(x^2\)	\(+\)	\(2x\)	\(-\)	\(3\)
			\(x^3\)	\(-\)	\(2x^2\)
					\(x^2\)	\(+\)	\(2x\)	\(-\)	\(3\)
					\(x^2\)	\(-\)	\(2x\)
							\(4x\)	\(-\)	\(3\)
							\(4x\)	\(-\)	\(8\)
									\(5\)

Отже,\(x^3 - x^2 + 2 x - 3 = (x - 2) (x^2 + x + 4 ) + 5\text{.}\)

\(p(x)\)Дозволяти поліном в\(F[x]\) і\(\alpha \in F\text{.}\) Ми говоримо, що\(\alpha\) це нуль або корінь\(p(x)\) якщо\(p(x)\) знаходиться в ядрі оцінки гомоморфізму\(\phi_{\alpha}\text{.}\) Все, що ми дійсно говоримо тут,\(\alpha\) це нуль \(p(x)\)якщо\(p(\alpha) = 0\text{.}\)

Слідство\(17.8\)

\(F\)Дозволяти бути полем. \(\alpha \in F\)Елемент дорівнює нулю\(p(x) \in F[x]\) if і тільки якщо\(x - \alpha\) є коефіцієнтом\(p(x)\) in\(F[x]\text{.}\)

Доказ

Припустимо, що\(\alpha \in F\) і\(p( \alpha ) = 0\text{.}\) За алгоритмом ділення існують поліноми\(q(x)\) і\(r(x)\) такі, що

\[ p(x) = (x -\alpha) q(x) + r(x) \nonumber \]

і ступінь\(r(x)\) повинна бути меншою за ступінь\(x -\alpha\text{.}\) з\(r(x)\) Оскільки ступінь менше 1,\(r(x) = a\)\(a \in F\text{;}\) тому,

\[ p(x) = (x -\alpha) q(x) + a\text{.} \nonumber \]

Але

\[ 0 = p(\alpha) = 0 \cdot q(\alpha) + a = a; \nonumber \]

отже,\(p(x) = (x - \alpha) q(x)\text{,}\) і\(x - \alpha\) є фактором\(p(x)\text{.}\)

І навпаки, припустимо, що\(x - \alpha\) це фактор\(p(x)\text{;}\) сказати\(p(x) = (x - \alpha) q(x)\text{.}\) Тоді\(p( \alpha ) = 0 \cdot q(\alpha) = 0\text{.}\)

 

Слідство\(17.9\)

\(F\)Дозволяти бути полем. Ненульовий многочлен\(p(x)\) ступеня\(n\) in\(F[x]\) може мати не більше\(n\) різних нулів у\(F\text{.}\)

Доказ

Ми будемо використовувати індукцію на ступінь\(p(x)\text{.}\) If\(\deg p(x) = 0\text{,}\)\(p(x)\) then є постійним многочленом і не має нулів. Нехай\(\deg p(x) = 1\text{.}\) Тоді\(p(x) = ax + b\) для деяких\(a\) і\(b\) в\(F\text{.}\) Якщо\(\alpha_1\) і\(\alpha_2\) є нулями\(p(x)\text{,}\) то\(a\alpha_1 + b = a\alpha_2 +b\) або\(\alpha_1 = \alpha_2\text{.}\)

Тепер припустимо, що\(\deg p(x) \gt 1\text{.}\) Якщо\(p(x)\) не має нуль в\(F\text{,}\) то ми зробили. З іншого боку, якщо\(\alpha\) дорівнює нулю,\(p(x)\text{,}\) то\(p(x) = (x - \alpha ) q(x)\) для деяких\(q(x) \in F[x]\) по Слідство 17.8. Ступінь\(q(x)\) -\(n-1\) за пропозицією 17.4. \(\beta\)Дозволяти якийсь інший нуль з\(p(x)\) того, що відрізняється від\(\alpha\text{.}\) Тоді\(p(\beta) = (\beta - \alpha) q(\beta) = 0\text{.}\) Оскільки\(\alpha \neq \beta\) і\(F\) є полем,\(q(\beta ) = 0\text{.}\) За нашою індукційною гіпотезою,\(q(x)\) може мати щонайбільше\(n - 1\) нулів в тому,\(F\) що відрізняються від\(\alpha\text{.}\) Тому, \(p(x)\)має не більше\(n\) різних нулів у\(F\text{.}\)

\(F\)Дозволяти бути полем. Монічний многочлен\(d(x)\) є найбільшим спільним дільником многочленів,\(p(x), q(x) \in F[x]\) якщо\(d(x)\) рівномірно ділить обидва\(p(x)\) і,\(q(x)\text{;}\) і, якщо для будь-якого іншого многочлена,\(d'(x)\) діливши обидва,\(p(x)\) і\(q(x)\text{,}\)\(d'(x) \mid d(x)\text{.}\) запишемо\(d(x) = \gcd( p(x), q( x))\text{.}\) Two \(p(x)\)многочлени і\(q(x)\) є відносно простими, якщо\(\gcd(p(x), q(x) ) = 1\text{.}\)

Пропозиція\(17.10\)

\(F\)Дозволяти поле і припустимо, що\(d(x)\) є найбільшим спільним дільником двох\(q(x)\) многочленів\(p(x)\) і в\(F[x]\text{.}\) Тоді існують\(r(x)\) многочлени і\(s(x)\) такий, що

\[ d(x) = r(x) p(x) + s(x) q(x)\text{.} \nonumber \]

Крім того, найбільший спільний дільник двох многочленів є унікальним.

Доказ

\(d(x)\)Дозволяти монічний многочлен найменшого ступеня в множині

\[ S = \{ f(x) p(x) + g(x) q(x) : f(x), g(x) \in F[x] \}\text{.} \nonumber \]

Ми можемо написати\(d(x) = r(x) p(x) + s(x) q(x)\) для двох поліномів\(r(x)\) і\(s(x)\) в\(F[x]\text{.}\) Нам потрібно показати, що\(d(x)\) ділить обидва\(p(x)\) і\(q(x)\text{.}\) Ми спочатку покажемо, що\(d(x)\) ділить\(p(x)\text{.}\) За алгоритмом ділення існують поліноми\(a(x)\) і\(b(x)\) такі, що \(p(x) = a(x) d(x) + b(x)\text{,}\)\(b(x)\)де або нульовий многочлен, або\(\deg b(x) \lt \deg d(x)\text{.}\) Тому

\ почати {вирівнювати*} б (х) & = р (х) - а (х) д (х)\ & = р (х) - а (х) (х) (r (x) p (x) + s (x) q (x))\ & = p (x) r (x) p (x) - a (x) s (x) s (x) q (x)\\ & = р (х) (1 - а (х) р (х)) + q (x) (x) (- a (x) s (x))\ end {вирівнювати*}

є лінійною комбінацією\(p(x)\)\(q(x)\) і, отже, повинен бути в\(S\text{.}\) Однак,\(b(x)\) повинен бути нульовим поліномом, оскільки\(d(x)\) був обраний як найменший ступінь; отже,\(d(x)\) ділить\(p(x)\text{.}\) Симетричний аргумент показує, що також\(d(x)\) повинен ділити\(q(x)\text{;}\) отже,\(d(x)\) є загальним дільником\(p(x)\) і\(q(x)\text{.}\)

Щоб показати, що\(d(x)\) є найбільшим спільним дільником\(p(x)\) і\(q(x)\text{,}\) припустимо, що\(d'(x)\) це ще один спільний дільник\(p(x)\) і\(q(x)\text{.}\) Ми покажемо, що\(d'(x) \mid d(x)\text{.}\) Since\(d'(x)\) є загальним дільником\(p(x)\) і\(q(x)\text{,}\) існують поліноми\(u(x)\) і \(v(x)\)такі, що\(p(x) = u(x) d'(x)\) і\(q(x) = v(x) d'(x)\text{.}\) тому,

\ почати {вирівнювати*} д (х) & = r (x) p (x) + s (x) q (x)\ & = r (x) u (x) d' (x) + s (x) v (x) d' (x) d' (x)\ & = d' (x) u (x) +s (x) v (x)]\ текст {}. \ end {вирівнювати*}

Так як\(d'(x) \mid d(x)\text{,}\)\(d(x)\) є найбільшим спільним дільником\(p(x)\) і\(q(x)\text{.}\)

Нарешті, ми повинні показати, що найбільший спільний дільник\(p(x)\) і\(q(x)\) є унікальним. Припустимо, що\(d'(x)\) це ще один найбільший спільний дільник\(p(x)\) і\(q(x)\text{.}\) Ми тільки що показали, що існують\(u(x)\) многочлени і\(v(x)\) в\(F[x]\) таких, що\(d(x) = d'(x)[r(x) u(x) + s(x) v(x)]\text{.}\) з

\[ \deg d(x) = \deg d'(x) + \deg[r(x) u(x) + s(x) v(x)] \nonumber \]

і\(d(x)\) і\(d'(x)\) обидва найбільші спільні дільники,\(\deg d(x) = \deg d'(x)\text{.}\) Оскільки\(d(x)\) і\(d'(x)\) обидва монічні многочлени однакового ступеня, це повинно бути так\(d(x) = d'(x)\text{.}\)

Зверніть увагу на схожість між доказом пропозиції\(17.10\) та доказом теореми\(2.10\).