Dashboard

Now you are in the subtree of Lecture Notes public knowledge tree. 

1. Кольцо многочленов над полем. Наибольший общий делитель. Алгоритм Евклида, линейное выражение НОД

Created about 11 years ago, updated 3 days ago

Разложение в кольце многочленов

$K$ – целостное кольцо (кольцо без делителей 0).

$ \mathbb{Z}, \mathbb{F}[X], A[X]$ над целостным кольцом $A$.

Обратимые элементы – регулярные.

$ f \in \mathbb{F}$ – обратим $\Rightarrow \deg{f}=0$

$a$ делится на $b$, если $a=bc ~~ b|a$

$a|b$ и $b|a \Rightarrow a,b$ – ассоциированы.

$p$ – простой, если $p$ нельзя представить в виде $p=ab$, где $a,b$ – необратимые.

Простой элемент $\mathbb{F}[X]$ – неприводимый многочлен.

Свойства делимости

  1. $a|b, b|c \Rightarrow a|c$

  2. $c|a, c|b \Rightarrow c|(a \pm b)$

  3. $a|b \Rightarrow a|bc$

  4. $b_1,...,b_m$ делится на $a \Rightarrow b_1c_1+...+b_mc_m$ делится на $a$

Определение. $K$ – факториальное кольцо, если любой элемент $a \in K$ можно представить в виде
$a=up_1...p_k~ (u$ – обратим, $p_i$ – простой) единственным образом.

$a=vq_1...q_m \Rightarrow m=k ~~ (q_i=u_ip_i, u_i$ – обратимый элемент).

Теорема. Пусть $K$ – произвольное целостное кольцо с разложением на множители. Тогда факториальность $K$
эквивалентна утверждению: любой $p$ – простой, делящий $ab$, делит по крайней мере один из множителей.

НОД и НОК в кольцах

$a,b \in K$

$d=$ НОД$(a,b)$, если:

  1. $d|a$ и $d|b$

  2. $c|a$ и $c|b \Rightarrow c|d$

НОД$(a,b)$ определен с точностью до ассоциированных элементов.

$a,b$ – ассоциированные, если $a=ub, u$ – обратимый.

Свойства

  1. НОД$(a,b)=a \Rightarrow a|b$

  2. НОД$(a,0)=a$

  3. НОД$(ta,tb)=t$НОД$(a,b)$

  4. НОД(НОД$(a,b),c)$ = НОД$(a,$ НОД$(b,c))$

$m=$ НОК$(a,b)$, если

  1. $a|m$ и $b|m$

  2. $a|c$ и $b|c \Rightarrow m|c$

Теорема

а) НОК$(a,b)=0 \Rightarrow a=0$ или $b=0$

б) $ab \neq 0, ~~m=$ НОК$(a,b), ~~ab=dm \Rightarrow d=$ НОД$(a,b)$

Признак делимости

$a,b$ – элементы факториального кольца.

$a=u_1p_1^{k_1}...p_m^{k_m}$

$b=u_2p_1^{l_1}...p_m^{l_m}$

  1. $a|b \Leftrightarrow k_i \leqslant l_i$

  2. НОД$(a,b)=p_1^{s_1}...p_m^{s_m},~~s_i=min(k_i,l_i)$

  3. НОК$(a,b)=p_1^{t_1}...p_m^{t_m},~~t_i=max(k_i,l_i)$

Факториальность евклидовых колец

$K$ – целостное кольцо.

$\delta: K \setminus \{0\} \rightarrow \mathbb{N} \cup \{0\}$

E1) $\delta(ab) \geqslant \delta(a)$ для любых $a,b \in K \setminus \{0\}$

E2) каковы бы ни были $a,b~(b \neq 0)$, найдутся такие $q,r$:

$a=qb+r,~\delta(r) < \delta(b)$

Пример. $K=\mathbb{Z},~\delta(a)=|a|$

$K=\mathbb{F}[X],~\delta(a)=\deg{a}$

Алгоритм Евклида нахождения НОД$(a,b)$

$a=q_1b+r_1,~\delta(r_1) < \delta(b)$

$b=q_2r_1+r_2,~\delta(r_2) < \delta(r_1)$

...

$r_{k-2}=q_kr_{k-1}=r_k,~\delta(r_k) < \delta(r_{k-1})$

$r_{k-1}=q_{k+1}r_k \Rightarrow r_k=$ НОД$(a,b)$

$\blacktriangle~r_k|r_{k-1} \Rightarrow r_k|r_{k-2} \Rightarrow ... \Rightarrow r_k|r_2,~r_k|r_1 \Rightarrow r_k|a,~r_k|b.$

$c|a,~c|b \Rightarrow c|r_k$

$\Downarrow$

$c|r_1 \Rightarrow c|r_2 \Rightarrow ... \Rightarrow c|r_k$

$\Rightarrow r_k=$ НОД$(a,b)~\blacksquare$

Теорема (линейное выражение НОД). В евклидовом кольце $K$ любые два элемента $a,b$ имеют НОД и НОК. При помощи алгоритма Евклида можно найти $u,v \in K\colon$ НОД$(a,b)=ua+vb$

$\blacktriangle~ r_1=a-q_1b \Rightarrow r_1=u_1a+v_1b \Rightarrow ... \Rightarrow r_k=ua+vb~ \blacksquare$

Следствие. $a,b$ – взаимно простые $\Leftrightarrow \exists u,v \in K\colon au+bv=1$

  1. НОД$(a,b)=1,~$НОД$(a,c)=1 \Rightarrow$ НОД$(a,bc)=1$

  2. $a|bc$, НОД$(a,b)=1 \Rightarrow a|c$

  3. $b|a,~c|a$, НОД$(b,c)=1 \Rightarrow bc|a$

$\blacktriangle~ $

  1. $au_1+bv_1=1,~au_2+cv_2=1$

$a^2u_1u_2+bav_1u_2+acu_1v_2+bcv_1v_2=1$

$a(au_1u_2+bv_1u_2+cu_1v_2)+bcv_1v_2=1 \Rightarrow a \cdot u+bc \cdot v=1$
$%Как делать внизу фигурную скобку?%$

  1. $au+bv=1$

$ac \cdot u+bc \cdot v=c$

$bc=aw$

$a(cu+wv)=c \Rightarrow a|c$

  1. $b|a,~c|a \Rightarrow$ НОК$(b,c)|a \Rightarrow bc|a$ (т.к. НОД$(b,c)=1$)$ ~\blacksquare$

Лемма. Любое евклидово кольцо является кольцом с разложением.

$\blacktriangle~ a=bc;~b,c$ – необратимые.

$\delta(b) < \delta(a)$

$\delta(b) \leqslant \delta(bc) = \delta(a)$

$b=qa+r,~\delta(r) < \delta(a)$

$r=0:~~ b=qa \Rightarrow \delta(b) = \delta(a)$

$b$ и $a$ – ассоциированы, $b=ua$ – противоречие.

$a=bc$

Докажем, что $1-qc \neq 0$.

Пусть $1-qc=0 \Rightarrow c$ обратим – противоречие.

Допустим, $\delta(a) = \delta(b) \leqslant \delta(b(1-qc)) = \delta(b-qa) = \delta(r) < \delta(a) \Rightarrow \delta(b) < \delta(a)$

$a=a_1...a_m,~a_i$ – необратимые.

$a_1...a_{k-1}$ – делитель $a_1...a_k$

$\delta(a) = \delta(a_1...a_m) > \delta(a_1...a_{m-1}) > \delta(a_1...a_{m-2}) > ... > \delta(a_1) > \delta(1)$

$m \leqslant \delta(a)$

Разложение с максимальным количеством множителей – разложение $a.~\blacksquare$

Теорема. Всякое евклидово кольцо факториально.

$\blacktriangle~ p$ – простой элемент кольца $K$

$p|bc \Rightarrow p|b$ или $p|c$

$b=0$ или $c=0$ – очевидно.

$b,c \neq 0;~d=$ НОД$(b,p)$

$d=p \Rightarrow p|b$

$d=1 \Rightarrow (a|bc,$ НОД$(a,b)=1 \Rightarrow a|c)$

$p|c ~\blacksquare$

Следствие. Кольца $\mathbb{Z}$ и $\mathbb{F}[X]$ факториальны.

$\mathbb{F}[x_1...x_n]$ – неевклидово, тем не менее $\mathbb{F}[x_1...x_n]$ – факториально.

$\delta(a)=|a|$ в случае $\mathbb{Z}.~~\delta(a)=\deg{a}$ в случае $\mathbb{F}[X].$

Неприводимые многочлены

Неприводимые многочлены – простые элементы в $\mathbb{F}[X]$

Над любым конечным полем существуют неприводимые многочлены сколь угодно высокой степени.

$f$ – неприводимый многочлен над $\mathbb{Z}[X] \Rightarrow f$ – неприводимый многочлен над $\mathbb{Q}[X]$

Критерий неприводимости Эйзенштейна

$f(x)=x^n+a_1x^{n-1}+...+a_n$

$a_1,..,a_n$ делятся на простое $p$, при этом $a_n$ не делится на $p^2 \Rightarrow f$ – неприводим над $\mathbb{Q}$.

$\blacktriangle~ f$ – приводим $\Rightarrow f=(x^s+b_1x^{s-1}+...+b_s)(x^t+...+c_t)$ над $\mathbb{Z}_p,~f \in \mathbb{Z}_p[X]=x^n$

$x^n=(x^s+b_1s^{s-1}+...+b_s)(x^t+...+c_t)=x^s \cdot x^t$

$b_s$ делится на $p,~c_t$ делится на $p$.

$a_n=b_sc_t \Rightarrow a_n$ делится на $p^2$ – противоречие. $\blacksquare$