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

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

$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$
$%Как делать внизу фигурную скобку?%$

2) $au+bv=1$

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

$bc=aw$

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

3) $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$