Return to gcd.tex CVS log

Up to [local] / OpenXM / doc / compalg

Annotation of OpenXM/doc/compalg/gcd.tex, Revision 1.1

1.1     ! noro        1: \chapter{$BB?9`<0$N(B GCD}
        !             2: \section{Euclid $B$N8_=|K!(B}
        !             3: $R$ $B$r(B UFD (Unique Factorization Domain; $B0l0UJ,2r@00h(B) $B$H$7(B, $R$ $B$K$*(B
        !             4: $B$1$k(B GCD $B$N7W;;$,2DG=$G$"$k$H$9$k(B. $B$3$N$H$-(B, $BB?9`<04D(B $R[x]$ $B$K$*$$$F(B
        !             5: $B$b(B GCD $B$N7W;;$,2DG=$H$J$k(B. $R$ $B$N>&BN$r(B $Q(R)$ $B$H=q$/(B.
        !             6: \begin{df}
        !             7: $$f = \sum_{i=0}^n (a_i/b_i) x^i\in Q(R)[x]\quad (a_i, b_i \in R; \GCD(a_i,b_i) = 1)$$ $B$KBP$7(B $f$ $B$N(B{\bf $BMFNL(B} $\cont(f)$ $B$r(B $$\cont(f) = \GCD(a_0,\cdots,a_n)/\LCM(b_0,\cdots,b_n),$$ $f$ $B$N(B {\bf primitive part} $\pp(f)$ $B$r(B $$\pp(f) = f/\cont(f)$$ $B$GDj5A$9$k(B. $\cont(f)$ $B$,(B $R$ $B$NC185$H$J$k$h$&$J(B $f$ $B$r86;OB?9`<0$H8F$V(B.
        !             8: \end{df}
        !             9:
        !            10: \begin{pr}
        !            11: $\pp(f)$ $B$O86;OE*(B.
        !            12: \end{pr}
        !            13: \proof
        !            14: $G=\GCD(a_0,\cdots,a_n),L=\LCM(b_0,\cdots,b_n)$
        !            15: $B$H=q$/(B.
        !            16: $\pp(f)=\sum_i L/b_i\cdot a_i/G\cdot x^i$ $B$h$j(B,
        !            17: $\cont(\pp(f)) = \GCD(L/b_0\cdot a_0/G, \cdots) \in R.$
        !            18:  $BAG85(B $p$ $B$,1&JU$r3d$k$H$9$k(B. $B$b(B
        !            19: $B$7(B, $B$"$k(B $j$ $B$KBP$7(B $p | (a_j/G)$ $B$J$i$P(B, $i\neq j$ $B$J$kG$0U$N(B $i$ $B$K(B
        !            20: $BBP$7(B$p {\not|} (a_i/G)$ $B$h$j(B $i \neq j$ $B$N$H$-(B $p|(L/b_i)$. $B0lJ}(B, $BG$0U$N(B
        !            21: $p$$B$KBP$7(B $p{\not|}(L/b_k)$ $B$J$k(B $k$ $B$OB8:_$9$k$+$i(B $k=j$. $B$3$N;~(B,
        !            22: $p|b_j$$B$H$J$j(B $\GCD(a_j,b_j)=1$ $B$KH?$9$k(B. $B$h$C$FA4$F$N(B $i$ $B$KBP$7(B,
        !            23: $p|(L/b_i)$ $B$3$l$OIT2DG=(B. $B$h$C$F(B $\cont(\pp(f)) = 1$. \qed
        !            24:
        !            25: \begin{lm}[Gauss]
        !            26: $f,g \in Q(R)[x]$ $B$KBP$7(B, $\cont(fg) = \cont(f)\cont(g).$
        !            27: \end{lm}
        !            28:
        !            29: \begin{pr}
        !            30: $f, g \in R[x]$ $B$KBP$7(B,
        !            31: $\GCD(f,g) = \GCD(\cont(f),\cont(g))\GCD(\pp(f),\pp(g))$
        !            32: $B$^$?(B, $f, g \in R[x]$ $B$r86;OB?9`<0$H$9$k$H(B,
        !            33: $\GCD(f,g) = \pp(\GCD_{Q(R)}(f,g))$
        !            34: $B$3$3$G(B, $\GCD_{Q(R)}(f,g)$ $B$O(B, $BBN(B $Q(R)$ $B>e$N0lJQ?tB?9`<04D$K$*$1$k(B
        !            35: GCD $B$r0UL#$9$k(B.
        !            36: \end{pr}
        !            37:
        !            38: $B0J>e$K$h$j(B, $BB?9`<0$N(B GCD $B$O(B, $B78?t4D$N(B GCD $B$*$h$S(B, $B78?t4D$N>&BN$G$N(B
        !            39: GCD $B$K$h$j7W;;$G$-$k$3$H$,$o$+$C$?(B. $B$7$+$7(B, $B<B:]$K>&BN$G$N1i;;$r(B
        !            40: $BMQ$$$k$3$H$O(B, $BL5BL$J(B GCD $B7W;;$rA}$d$9$@$1$H$J$k(B. $B=>$C$F(B, $B$^$:(B,
        !            41: $BB?9`<0$N=|;;$G(B, $B>&BN$N=|;;$,8=$l$J$$$b$N$r9M$($k(B.
        !            42:
        !            43: \begin{df}
        !            44: $f,g \in R[x]$, $\deg(f) \ge \deg(g)$ $B$KBP$7(B $f$ $B$N(B $g$ $B$K$h$k5<>jM>(B
        !            45: (pseudo-remainder) $\prem(f,g)$ $B$r(B
        !            46: $$\prem(f,g) = {\rm remainder}(\lc(g)^{\deg(f)-\deg(g)+1}f,g)$$
        !            47: $B$HDj5A$9$k(B. $B$3$3$G(B, ${\rm remainder}(f,g)$ $B$O(B, $BDL>o$NB?9`<0=|;;$G$"$k(B.
        !            48: \end{df}
        !            49:
        !            50: $BMF0W$K$o$+$k$h$&$K(B, $\prem(f,g)$ $B$N7W;;$NESCf$K8=$l$k=|;;$O(B,
        !            51: $BA4$F(B $R$ $B>e$N@0=|$G$"$k(B. $B$3$l$rMQ$$$F(B, Euclid $B$N8_=|K!$r5-=R$9$k$H(B
        !            52: $B<!$N$h$&$K$J$k(B.
        !            53:
        !            54: \begin{al}
        !            55: \label{euclid}
        !            56: \begin{tabbing}
        !            57: \\
        !            58: Input : $B86;OE*B?9`<0(B $f_1, f_2 \in R[x]$, $\deg(f_1) \ge \deg(f_2)$\\
        !            59: Output : $\GCD(f_1,f_2)$\\
        !            60: $i \leftarrow 1$\\
        !            61: do \= \{\\
        !            62: \> $f_{i+2} \leftarrow \prem(f_i,f_{i+1})$\\
        !            63: \> if \= ( $f_{i+2} = 0$ ) then return $\pp(f_{i+1})$\\
        !            64: \> $i \leftarrow i+1$\\
        !            65: \}
        !            66: \end{tabbing}
        !            67: \end{al}
        !            68:
        !            69: \begin{df}
        !            70: $f_1, f_2$ $B$KBP$7(B, $\beta_i f_{i+1} = {\rm remainder}(\alpha_i f_{i-1},f_i)$ $B$J$k=|(B
        !            71: $B;;$K$h$j@8@.$5$l$kNs(B $\{f_i\}$ $B$rB?9`<0>jM>Ns$H8F$V(B.
        !            72: \end{df}
        !            73:
        !            74: \section{$B3HD%(B Euclid $B8_=|K!(B}
        !            75: $BBN(B $K$ $B>e$N0lJQ?tB?9`<04D(B $K[x]$ $B$O(B PID (Principal Ideal Domain; $BC19`(B
        !            76: $B%$%G%"%k@00h(B) $B$G$"$k(B. $B$3$N>l9g(B, $f, g \in K[x]$ $B$KBP$7(B, $B%$%G%"%k(B
        !            77: $(f,g)$$B$N@8@.85$,(B, $\GCD(f,g)$ $B$H$J$k(B. $B$9$J$o$A(B$a, b \in K[x]$ $B$,B8:_(B
        !            78: $B$7$F(B,
        !            79: $$af+bg=\GCD(f,g)$$ $B$H=q$1$k(B. $B$3$N78?t(B $a, b$
        !            80: $B$O(B, Euclid $B$N8_=|K!$NJQ7A$K$h$j5a$a$k$3$H$,$G$-$k(B.
        !            81:
        !            82: \begin{al}
        !            83: \begin{tabbing}
        !            84: \\
        !            85: Input : $B86;OE*B?9`<0(B $f_1, f_2 \in K[x]$, $\deg(f_1) \ge \deg(f_2)$\\
        !            86: Output : $\GCD(f_1,f_2)$ $B$*$h$S(B $af_1+bf_2=\GCD(f_1,f_2)$ $B$J$k(B $a, b \in K[x]$\\
        !            87: $a_1 \leftarrow 1$, $a_2 \leftarrow 0$, $b_1 \leftarrow 0$, $b_2 \leftarrow 1$\\
        !            88: $i \leftarrow 1$\\
        !            89: do \= \{\\
        !            90: \> $\deg(f_i - q_i f_{i+1}) < \deg(f_{i+1})$ $B$J$k(B $q_i$ $B$r5a$a$k(B\\
        !            91: \> $f_{i+2} \leftarrow f_i - q f_{i+1}$;
        !            92: \quad $a_{i+2} \leftarrow a_i - q a_{i+1}$;
        !            93: \quad $b_{i+2} \leftarrow b_i - q b_{i+1}$\\
        !            94: \> if \= ( $f_{i+2} = 0$ ) then return $\{f_{i+1},a_{i+1},b_{i+1}\}$\\
        !            95: \> $i \leftarrow i+1$\\
        !            96: \}
        !            97: \end{tabbing}
        !            98: \end{al}
        !            99: $B$3$3$G8=$l$?(B $a_i, b_i$ $B$KBP$7(B,
        !           100: $$\deg(a_i) \le \deg(f_2)-\deg(f_{i-1}),\quad \deg(b_i) \le \deg(f_1)-\deg(f_{i-1})$$
        !           101: $B$G$"$k$3$H$o$+$k(B.
        !           102: $BFC$K(B, $f = f_i = \GCD(f_1,f_2)$ $B$J$i$P(B
        !           103: $$\deg(a_i) < \deg(f_2)-\deg(f), \quad \deg(b_i) < \deg(f_1)-\deg(f).$$
        !           104:
        !           105: \begin{pr}
        !           106: $f, g \in K[x]$ $B$KBP$7(B, $h = \GCD(f,g)$ $B$H$9$k$H(B,
        !           107: $af+bg=\GCD(f,g)$ $B$+$D(B $\deg(a) < \deg(g) - \deg(h),\quad \deg(b) < \deg(f) - \deg(h)$
        !           108: $B$J$k(B $a, b \in K[x]$ $B$OB8:_$7$F0l0UE*(B.
        !           109: \end{pr}
        !           110: \proof
        !           111: $B0l0U@-$N$_<($;$P$h$$(B. $h$ $B$GN>JU$r3d$C$F(B, $h=1$ $B$H$7$F$h$$(B.
        !           112: $$af+bh=1, \quad a_1f+b_1g=1,$$
        !           113: $$\deg(a)<\deg(g),\quad \deg(b)<\deg(f),\quad \deg(a_1)<\deg(g),\quad \deg(b_1)<\deg(f)$$
        !           114: $B$H$9$k$H(B, $(a-a_1)f+(b-b_1)g=0$ $B$+$D(B $\GCD(f,g)=1$ $B$h$j(B
        !           115: $g|(a-a_1).$
        !           116: $\deg(a-a_1)<\deg(g)$ $B$h$j(B $a-a_1=b-b_1=0.$\qed\\
        !           117: $af+bg=1$ $B$J$i$P(B $af \equiv 1 \bmod g$
        !           118: $B$9$J$o$A(B, $B>jM>4D(B $K[x]/(g)$ $B$K$*$$$F(B
        !           119: $a \bmod g = (f \bmod g)^{-1}$
        !           120: $B$G$"$k(B.
        !           121: $B>jM>4D$K$*$1$k5U857W;;$O(B, $B7W;;5!Be?t$K$*$$$FIQHK$KI,MW$H$J$j(B,
        !           122: $BFC$K8e$G=R$Y$k(B modular $B%"%k%4%j%:%`$K$*$$$F6K$a$F=EMW$JLr3d$r1i$:$k(B.
        !           123:
        !           124: $B$3$NL?Bj$O(B, $B<!$N$h$&$K0lHL2=$G$-$k(B.
        !           125:
        !           126: \begin{pr}
        !           127: $f=\prod_{i=1}^n f_i \in K[x]$ $B$KBP$7(B, $f_i$ $B$,8_$$$KAG$G$"$k$H$9$k(B.
        !           128: $B$3$N$H$-(B,
        !           129: $$\sum_{i=1}^n e_i (f/f_i) =1, \quad \deg(e_i)<\deg(f_i)$$
        !           130: $B$J$k(B $e_i \in K[x]$ $B$,0l0UE*$KB8:_$9$k(B.
        !           131: \end{pr}
        !           132: \proof $B5"G<K!$K$h$j(B,
        !           133: $\sum_{i=1}^n E_i (f/f_i) =1$
        !           134: $B$J$k(B $E_i$ $B$,B8:_$9$k$3$H$,J,$+$k(B. $E_i = q_if_i+e_i$
        !           135: ($\deg(e_i)<\deg(f_i)$) $B$H=|;;$r9T$&$H(B,
        !           136: $$f\sum_{i=1}^n{q_i}+\sum_{i=1}^n e_i(f/f_i)=1.$$
        !           137: $B$3$3$G(B, $\deg(\sum_{i=1}^n e_i(f/f_i))<\deg(f)$ $B$h$j(B $\sum_{i=1}^n{q_i}=0$
        !           138: $B$,@.$jN)$D$+$i(B,
        !           139: $$\sum_{i=1}^n e_i (f/f_i) =1, \quad \deg(e_i)<\deg(f_i).$$
        !           140: $B$3$N$h$&$J(B $e_i$ $B$O(B $\bmod f_i$ $B$G0l0UE*$@$+$i(B, $\deg(e_i)<\deg(f_i)$
        !           141: $B$G$O0l0U$K7h$^$k(B.
        !           142: \qed
        !           143:
        !           144: \begin{pr}
        !           145: \label{exteuc}
        !           146: $f=\prod_{i=1}^n f_i \in K[x]$ $B$KBP$7(B, $f_i$ $B$,8_$$$KAG$G$"$k$H$9$k(B.
        !           147: $\deg(g)\le \deg(f)$ $B$J$i$P(B,
        !           148: $$\sum_{i=1}^n e_i (f/f_i) =g \quad \deg(e_i)\le \deg(f_i)$$
        !           149: $B$J$k(B $e_i \in K[x]$ $B$,B8:_$9$k(B. $BFC$K(B, $\deg(g)<\deg(f)$ $B$J$i$P(B,
        !           150: $\deg(e_i)< \deg(f_i)$ $B$H$G$-$F(B, $e_i$ $B$O0l0UE*(B.
        !           151: \end{pr}
        !           152: \proof
        !           153: $BA0L?Bj$HF1MM$K(B, $\sum_{i=1}^n E_i (f/f_i) =g$ $B$J$k(B $E_i$ $B$,B8:_$9$k(B.
        !           154: $E_i = q_if_i+e_i$ ($\deg(e_i)<\deg(f_i)$) $B$H=|;;$r9T$&$H(B,
        !           155: $$cf+\sum_{i=1}^n e_i(f/f_i)=(e_1+cf_1)(f/f_1)+\sum_{i=2}^n e_i(f/f_i)=g,
        !           156:  \quad c = \sum_{i=1}^n q_i$$
        !           157: $B$3$3$G(B, $\deg(\sum_{i=1}^n e_i(f/f_i))<\deg(f)$, $\deg(g)\le \deg(f)$ $B$h$j(B
        !           158: $\deg(cf)\le \deg(f)$ $B$9$J$o$A(B
        !           159: $\deg(c)\le 0.$ $B$h$C$F(B
        !           160: $\deg(e_1+cf_1) \le \deg(f_1).$
        !           161: $BFC$K(B, $\deg(g)<\deg(f)$ $B$J$i$P(B $c=0$ $B$h$j(B
        !           162: $\deg(e_1+cf_1) = \deg(e_1) < \deg(f_1).$
        !           163: $B0l0U@-$bA0L?Bj$HF1MM(B.
        !           164: \qed
        !           165:
        !           166: \begin{co}
        !           167: ({\bf $BItJ,J,?tJ,2r(B})
        !           168: \label{parfrac}
        !           169:
        !           170: $d, n \in K[x]$ ($\deg(n)<\deg(d)$)$B$H$7(B, $d=\prod_{i=1}^n d_i^i$ $B$r(B $d$ $B$NL5J?J}J,2r$H$9$l$P(B,
        !           171: $r_{ij} \in K[x]$ ($1\le j \le i, \deg(r_{ij}) < \deg(d_i)$) $B$,B8:_$7$F(B,
        !           172: $$n/d = \sum_{i=1}^n \sum_{j=1}^i r_{ij}/d_i^j.$$
        !           173: \end{co}
        !           174: \proof
        !           175: $D_i=d_i^i$ $B$H$*$1$P(B, $BA0L?Bj$K$h$j(B $\deg(E_i)<\deg(D_i)$ $B$J$k(B $E_i$ $B$,(B
        !           176: $BB8:_$7$F(B
        !           177: $n = \sum_{i=1}^n E_i(d/D_i).$
        !           178: $B$3$l$+$i(B
        !           179: $n/d=\sum_{i=1}^n E_i/d_i^i.$
        !           180: $E_i$ $B$r(B $d_i$ $B$NQQ$GE83+$9$l$P(B, $\deg(E_i)<\deg(d_i^i)$ $B$h$j(B
        !           181: $E_i=\sum_{j=1}^i r_{ij}d_i^{(i-j)},$ $\deg(r_{ij})<\deg(d_i)$
        !           182: $B$H=q$1$k(B. $B$h$C$F(B
        !           183: $E_i/d_i^i = \sum_{j=1}^i r_{ij}/d_i^j.$
        !           184: \qed
        !           185:
        !           186: \section{$B=*7k<0(B}
        !           187: $R$ $B$r2D494D$H$9$k(B.
        !           188: \begin{df}
        !           189: $$a(x)=\sum_{i=0}^n a_i x^i, \quad b(x)=\sum_{i=0}^m b_i x^i \quad (a_i, b_i \in R)$$
        !           190: $B$KBP$7(B, $a,b$ $B$N(B Sylvester $B9TNs(B $Syl(a,b)$ $B$r<!$GDj5A$9$k(B.
        !           191:
        !           192: \[ Syl(a,b) = \left[
        !           193: \begin{array}{cccccc}
        !           194: a_n & a_{n-1} & \cdots & a_0 & & \\
        !           195:     & \cdots  & \cdots & \cdots & \cdots &  \\
        !           196:     &         & a_n    & a_{n-1} & \cdots & a_0   \\
        !           197: b_m & b_{m-1} & \cdots & b_0 & & \\
        !           198:     & \cdots  & \cdots & \cdots & \cdots &  \\
        !           199:     &         & b_m    & b_{m-1} & \cdots & b_0   \\
        !           200: \end{array}
        !           201: \right]
        !           202: \]
        !           203:
        !           204: $a,b$ $B$N=*7k<0(B $\res_x(a,b)$ $B$r(B $\res_x(a,b)=\det(Syl(a,b))$
        !           205: $B$GDj5A$9$k(B.
        !           206: \end{df}
        !           207:
        !           208: \begin{lm}
        !           209: $\deg(s)<\deg(b), \deg(t)<\deg(a)$ $B$J$k(B $s,t \in R[x]$ $B$,B8:_$7$F(B $sa+tb=0$
        !           210:
        !           211: $\Leftrightarrow s(x)=\sum_{i=0}^{m-1} s_i x^i, \quad t(x)=\sum_{i=0}^{n-1} t_i x^i$ $B$H=q$/$H$-(B
        !           212: \begin{equation}
        !           213: \label{syleq}
        !           214: [s_{m-1},\cdots, s_1, s_0, t_{n-1}\,\cdots,t_1, t_0] Syl(a,b) = [0,\cdots,0]
        !           215: \end{equation}
        !           216: \end{lm}
        !           217:
        !           218: \begin{co}
        !           219: $R$ $B$,@00h$H$9$k(B.
        !           220: $\deg(s)<\deg(b), \deg(t)<\deg(a)$ $B$J$k(B $s,t \in R[x]\setminus \{0\}$
        !           221: $B$,B8:_$7$F(B $sa+tb=0 \Leftrightarrow \res_x(a,b)=0$
        !           222: \end{co}
        !           223:
        !           224: \begin{pr}
        !           225: $R$ $B$,(B UFD $B$H$9$k(B. ($R[x]$ $B$K$*$$$F(B GCD $B$,(B well defined.) $a,b \in R[x]$ $B$K(B
        !           226: $BBP$7(B,
        !           227: $$\deg(\GCD(a,b))>0 \Leftrightarrow \res_x(a,b) = 0.$$
        !           228: \end{pr}
        !           229: \underline{$\Rightarrow$}\\
        !           230: $g=\GCD(a,b)$, $\deg(g)>0$ $B$H$9$k$H(B, $(b/g)\cdot a + (a/g)\cdot b=0.$
        !           231: $b/g$, $a/g$ $B$O(B (\ref{syleq}) $B$N(B 0 $B$G$J$$2r$r9=@.$9$k$+$i(B, $B7O$h$j(B
        !           232: $\res_x(a,b)=0$. \\
        !           233: \underline{$\Leftarrow$}\\
        !           234: $\res_x(a,b)=0$ $B$H$9$k$H(B, $B7O$h$j(B (\ref{syleq}) $B$N(B 0 $B$G$J$$2r$,B8:_$9$k(B.
        !           235: $B$9$J$o$A(B, $\deg(s)<\deg(b), \deg(t)<\deg(a)$ $B$J$k(B $s,t$ $B$,B8:_$7$F(B $sa+tb=0.$
        !           236: $\GCD(a,b)$$B$,Dj?t$J$i(B $a|t$ $B$H$J$k$,(B, $\deg(t)<\deg(a)$ $B$h$jIT2DG=(B. $B$h$C$F(B
        !           237: $\GCD(a,b)$ $B$ODj?t$G$J$$(B.\qed
        !           238:
        !           239: \section{$BItJ,=*7k<0(B}
        !           240: $B%"%k%4%j%:%`(B \ref{euclid} $B$O(B, $B3N$+$K>&BN>e$N1i;;$rI,MW$H$7$J$$$,(B, $B78?t$NKDD%$,Cx$7$$(B.
        !           241: $B<!$NNc$r9M$($F$_$k(B.
        !           242:
        !           243: \begin{ex}
        !           244: $$R = \Z,\quad f = x^8+x^5+1,\quad g = 3x^6+1$$
        !           245: $B$3$N>l9g(B, $BESCf$G@8@.$5$l$k5<>jM>$O(B,
        !           246: \begin{center}
        !           247: $27x^5-9x^2+27$\\
        !           248: $729x^3-2187x+729$\\
        !           249: $-13947137604x^2+94143178827x-20920706406$\\
        !           250: $5822950344611693220025353x-1293988965469265160005634$\\
        !           251: $-23353191009282740851191794693386216142000386817007672113424$
        !           252: \end{center}
        !           253: $B$H$J$j(B, $B7k2L$O(B $\GCD(f,g)=1$ $B$@$,78?t$ND9$5$,%9%F%C%WKh$KLs(B 2 $BG\$:$E(B
        !           254: $BA}$($F$$$k$3$H$,J,$+$k(B.
        !           255: \end{ex}
        !           256: $B<B:]$K$O(B, $B>e$NNc$G$O(B, $BESCf$G@8@.$5$l$k5<>jM>$O86;OE*$G$J$/(B,
        !           257: $BMFNL$r=|$/$H<!$N$h$&$K$J$k(B.
        !           258: \begin{center}
        !           259: $3x^5-x^2+3$\\
        !           260: $x^3-3x+1$\\
        !           261: $-4x^2+27x-6$\\
        !           262: $9x-2$\\
        !           263: $-1$
        !           264: \end{center}
        !           265:
        !           266: $B$3$N>l9g(B, $B5<>jM>$NMFNL$r<B:]$K(B GCD $B$rMQ$$$F7W;;$7$?$,(B, $B<B$O$"$kDxEY$N(B
        !           267: $BItJ,$O(B, $B<+F0E*$K<h$j=|$/$3$H$,$G$-$k(B. $B$3$N$?$a(B, $BItJ,=*7k<0(B  (subresultant)
        !           268: $B$rF3F~$9$k(B.
        !           269:
        !           270: \begin{df}
        !           271: $\displaystyle f = \sum_{i=0}^n a_i x^i, g = \sum_{i=0}^m b_i x^i$ $B$H$9$k$H$-(B,
        !           272: $f,g$ $B$N(B $j$ $B<!$NItJ,=*7k<0(B $S_j(f,g)$ $B$r<!$N9TNs<0$GDj5A$9$k(B.
        !           273:
        !           274: \[ S_j(f,g) = \left|
        !           275: \begin{array}{cccccc}
        !           276: a_n & a_{n-1} & \cdots & \cdots & \cdots & x^{m-j-1}f \\
        !           277:     & \cdots  & \cdots & \cdots & \cdots & \cdots \\
        !           278:     &         & a_n    & \cdots & a_{j+1}& f   \\
        !           279: b_m & b_{m-1} & \cdots & \cdots & \cdots & x^{n-j-1}g \\
        !           280:     & \cdots  & \cdots & \cdots & \cdots & \cdots \\
        !           281:     &         & b_m    & \cdots & b_{j+1}& g   \\
        !           282: \end{array}
        !           283: \right|
        !           284: \]
        !           285: $BFC$K(B, $S_0(f,g) = \res_x(f,g)$ ($B=*7k<0(B) $B$H$J$k(B.
        !           286: \end{df}
        !           287:
        !           288: \begin{df}
        !           289: $f \sim g$ $B$H$O(B $\pp(f) = \pp(g)$ $B$J$k$3$H(B.
        !           290: \end{df}
        !           291:
        !           292: \begin{pr}
        !           293: {\rm \cite{SUB}}
        !           294: $\deg(f_1) \ge \deg(f_2)$ $B$H$9$k(B. $f_1, f_2$ $B$+$i@8@.$5$l$kB?9`<0>jM>Ns(B
        !           295: $\{f_1, f_2, \cdots\}$ $B$KBP$7(B,
        !           296: $i \ge 3$ $B$J$i$P(B $f_i \sim S_{\deg(f_i)}$ $B$+$D(B $f_i \sim S_{\deg(f_{i-1})-1}.$
        !           297: \end{pr}
        !           298:
        !           299: $BItJ,=*7k<0$O(B, $BDj5A$K$h$j(B $R[x]$ $B$KB0$9$k(B. $B$h$C$F(B, $BB?9`<0>jM>Ns$NDj5A$K(B
        !           300: $B8=$l$k(B $\alpha_i, \beta_i$ $B$r$&$^$/<h$C$F(B, $f_i$ $B$,E,Ev$J(B $S_j$ $B$HEy$7(B
        !           301: $B$/$J$k$h$&$K$G$-$l$P(B, $B8=$l$k=|;;$OA4$F(B $R$ $B$K$*$1$k@0=|$H$J$k(B. $B$3$l$O(B
        !           302: $B<B:]$K2DG=$G$"$k(B.
        !           303:
        !           304: \begin{pr}
        !           305: $BB?9`<0>jM>Ns$r(B,
        !           306: $$d_i = \deg(f_i)-\deg(f_{i+1}),\quad \alpha_i = 1,$$
        !           307: $$\beta_2 = 1,\quad \beta_i = \lc(f_{i-1})\zeta_i^{d_{i-1}},$$
        !           308: $$\zeta_2 = 1,\quad \zeta_i = \lc(f_{i-1})^{d_{i-2}}\zeta_{i-1}^{(1-d_{i-2})},$$
        !           309: $$f_{i+1} = \prem(f_{i-1},f_i)/\beta_i$$
        !           310: $B$GDj$a$l$P(B,
        !           311: $$f_i = \pm S_{\deg(f_{i-1})-1}(f_1,f_2).$$
        !           312: \end{pr}
        !           313:
        !           314: $B$3$3$G(B, $B78?t$rITDj85$H$7$?$H$-(B, $B=*7k<0$,(B, $B$3$l$i78?t$N4{LsB?9`<0$G$"$k(B
        !           315: $B$3$H$,CN$i$l$F$$$k(B. $B$h$C$F(B, GCD $B$,(B 1 $B$K$J$k>l9g$r9M$($l$P(B, $B$3$NL?Bj$G(B
        !           316: $BDj$a$i$l$kB?9`<0>jM>Ns$O(B, $B0lHL$NB?9`<0$KBP$7$F:GBg$N78?t=|5n$r9T$J$C$F(B
        !           317: $B$$$k$H9M$($i$l$k(B. $B<B:]$K(B, $BA0$NNc$KE,MQ$7$F$_$k$H(B, \\
        !           318: \begin{center}
        !           319: $27x^5-9x^2+27$\\
        !           320: $27x^3-81x+27$\\
        !           321: $-36x^2+243x-54$\\
        !           322: $1971x-438$\\
        !           323: $-5329$
        !           324: \end{center}
        !           325: $B$H$J$j(B, $B86;OE*B?9`<0$H$7$?$b$N$K$O5Z$P$J$$$b$N$N(B, $B$+$J$j$N78?t$r=|5n$7$F$$$k(B
        !           326: $B$3$H$,$o$+$k(B.
        !           327:
        !           328: \section{Modular $B%"%k%4%j%:%`(B}
        !           329: $BA0@a$G=R$Y$?8_=|K!$K$h$k(B GCD $B$N7W;;$O(B, GCD $B$N<!?t$,Hf3SE*9b$$>l9g$K(B
        !           330: $B$ONI9%$KF0:n$9$k$,(B, GCD $B$N<!?t$,Dc$$>l9g(B, $BFC$K(B GCD $B$,(B 1 $B$N>l9g$J$I(B
        !           331: $B$G$O(B, $BItJ,=*7k<0K!$K$h$C$F$b78?t$NA}Bg$OHr$1$i$l$J$$(B. $B$3$N$h$&$JM}M3(B
        !           332: $B$+$i(B, GCD $B$O(B, {\bf modular $B%"%k%4%j%:%`(B}$B$K$h$j7W;;$5$l$k$3$H$,B?$$(B.
        !           333: modular $B%"%k%4%j%:%`$H$O(B, $B78?t4D$N>jM>4D$K$*$1$k1i;;7k2L$+$i$b$H$N(B
        !           334: $B4D>e$N7k2L$rF@$k%?%$%W$N%"%k%4%j%:%`$NAm>N$G$"$k(B. modular $B%"%k%4%j%:%`(B
        !           335: $B$K$O(B, $BCf9q>jM>DjM}$rMQ$$$k$b$N$H(B, Hensel $B9=@.$rMQ$$$k$b$N$,$"$k(B.
        !           336: $B8e<T$K$D$$$F$O0x?tJ,2r$N@a$G>\$7$/=R$Y$k$3$H$H$7(B, $B$3$3$G$O(B, $BA0<T$K(B
        !           337: $B$D$$$F=R$Y$k(B.
        !           338:
        !           339: \begin{pr}($BCf9q>jM>DjM}(B)
        !           340: $B2D494D(B $A$ $B$N%$%G%"%k(B $A_1,\cdots,A_r$ $B$NG$0U$NBP(B $(A_i,A_j) (i \neq j)$ $B$K(B
        !           341: $BBP$7(B,$A_i+A_j=A$ $B$J$i$P(B,
        !           342: $$\quad  A/\prod A_i \simeq \bigoplus A/A_i.$$
        !           343: \end{pr}
        !           344: \proof
        !           345:  $r=2$ $B$N$H$-$r<($9(B. $A_1+A_2=A$ $B$h$j(B $a_1+a_2=1$ $B$J$k(B
        !           346: $a_i\in A_i$ $B$,B8:_$9$k(B. $BG$0U$N(B $x, y \in A$ $B$KBP$7(B, $z = x a_2 + y
        !           347: a_1$ $B$HCV$/$H(B, $z \equiv x \pmod {A_1}$ $B$+$D(B $z \equiv y \pmod {A_2}$ $B$h$j(B,
        !           348: $BI8=`E*<LA|(B
        !           349: $$\phi : A \rightarrow A/A_1 \oplus A/A_2$$
        !           350: $B$OA4<M$+$D(B
        !           351: $\Ker(\phi) = A_1\cap A_2$ $B$h$j(B
        !           352: $A/A_1\cap A_2 \simeq A/A_1 \oplus A/A_2.$
        !           353: $B$3$3$G(B,
        !           354: $A_1 A_2 \subset A_1\cap A_2 = (A_1\cap A_2)\cdot(A_1+A_2) \subset A_1 A_2$
        !           355: $B$h$j(B, $A_1 A_2 = A_1\cap A_2.$
        !           356: $B$h$C$F(B
        !           357: $$A/A_1 A_2 \simeq A/A_1 \oplus A/A_2.$$
        !           358: $B0lHL$N>l9g$O(B, $A_1+A_2\cdots A_r \supset \prod_{i\ge 2}(A_1+A_i) \ni 1$
        !           359: $B$h$j5"G<K!$,;H$($k(B. \qed
        !           360:
        !           361: \begin{co}
        !           362: $A$ $B$r(B Euclid $B4D$H$9$k(B. $m_i \in A$ $B$,8_$$$KAG$J$i$P(B,
        !           363: $A/(\prod m_i) \simeq \bigoplus A/(m_i)$.
        !           364: \end{co}
        !           365:
        !           366: \begin{ex}
        !           367: $K$ $B$rBN$H$9$k(B. $f_i \in K[x]$ $B$,8_$$$KAG$J$i$P(B,
        !           368: $K[x]/(\prod f_i) \simeq \bigoplus K[x]/(f_i)$.
        !           369: \end{ex}
        !           370:
        !           371: $B$3$l$O(B, $BM-8BBN>e$N0x?tJ,2r$KMQ$$$i$l$k(B. $B$^$?(B, $f_i$ $B$H$7$F(B
        !           372: $x-a_i$ $B$J$k7A$N$b$N$r$H$l$P(B, $BJd4VK!$r$"$i$o$9$H9M$($i$l$k(B.
        !           373:
        !           374: \begin{ex}
        !           375: $m_i \in \Z$ $B$,8_$$$KAG$J$i$P(B,
        !           376: $\Z/(\prod m_i) \simeq \bigoplus \Z/(m_i)$.
        !           377: \end{ex}
        !           378:
        !           379: $B<!$NJdBj$O(B, modular $B1i;;$K$h$k%$%a!<%8$r$b$H$N6u4V$K0z$-La$9:]$K(B
        !           380: $B>o$KMQ$$$i$l$k(B.
        !           381:
        !           382: \begin{lm}
        !           383: $a \equiv a' \bmod A$, $|a| \le B$, $|a'| \le A/2$, $A > 2B$ $B$J$i$P(B,
        !           384: $a = a'$.
        !           385: \end{lm}
        !           386: \proof
        !           387: $a-a' = kA$ $B$H$9$k(B. $|a-a'| \le |a|+|a'| \le B+A/2 < A$ $B$h$j(B $k = 0$. \qed
        !           388:
        !           389: \vskip \baselineskip
        !           390: $BCf9q>jM>DjM}$N1~MQ$H$7$F(B, $\Z[x]$ $B$K$*$1$k(B GCD $B7W;;$rNc$K$H$k(B.
        !           391: $$f, g \in \Z[x],\quad h = \GCD(f,g) \in \Z[x]$$
        !           392: $B$H$9$k(B. $B$3$N;~(B,
        !           393: $$\GCD(f \bmod p_i,g \bmod p_i) = h \bmod p_i$$
        !           394: $B$J$kAG?t(B $p_i$ $B$,M?$($i$l$l$P(B, $B78?t$KBP$7$FCf9q>jM>DjM}(B
        !           395: $B$rE,MQ$7$F(B,
        !           396: $$m=\prod p_i | (h - h_1)$$
        !           397: $B$J$k(B $h_1$ $B$r9=@.$G$-$k(B. $B$3$3$G(B,
        !           398: $m$ $B$,==J,Bg$-$1$l$P(B, $h_1$ $B$NK!(B $m$ $B$G$N0l0U@-$K$h$j(B, $h_1$ $B$N78?t$K(B
        !           399: $m$ $B$r2C8:$7$F78?t$N@dBPCM$r(B $m/2$ $B0J2<$H$7$?$b$N$O(B, $h$ $B$H0lCW$9$k(B.
        !           400: $BLdBj$O(B, $B$"$i$+$8$a(B, $BK!(B $p_i$ $B$G$N(B GCD $B$,(B, $B??$N(B GCD $B$NA|$H$J$C$F$$$k(B,
        !           401: $B$9$J$o$ABEEv$G$"$k$+$I$&$+ITL@$G$"$k$H$$$&E@$G$"$k$,(B, $BBEEv$G$J$$(B $p$
        !           402: $B$OM-8B8D$7$+$J$$$3$H$,$o$+$k(B ($B8_$$$KAG$J>l9g$N=*7k<0$r9M$($l$P$h$$(B).
        !           403: $p$ $B$NBEEv@-$OK!(B $p$ $B$G$N(B GCD $B$N<!?t$,:GDc$H$$$&>r7o$GFCD'$E$1$i$l$k$?(B
        !           404: $B$a(B, $B$5$^$6$^$J(B $p$ $B$G$N(B GCD $B7W;;$r7+$jJV$9$3$H$K$h$jH=Dj$G$-$k(B.
        !           405:
        !           406: $B$3$N$[$+(B, $B@0?t$KBP$9$kCf9q>jM>DjM}$O(B, $B3HD%(B Euclid $B8_=|K!(B, $B9TNs<0(B, $B=*7k(B
        !           407: $B<0$N7W;;$KMQ$$$i$l$k(B. $B$3$NJ}K!$,8zNO$rH/4x$9$k$N$O(B, $B7k2L$NBg$-$5$KHf3S(B
        !           408: $B$7$F(B, $BESCf$N7W;;$K$*$$$FBg$-$J<0$,8=$l$k>l9g(B ($BCf4V<0KDD%(B)$B$G$"$k(B.  $B8=:_(B
        !           409: $B<gMW$J%7%9%F%`$K$*$$$F$O(B, GCD $B$O(B, $B8e$G=R$Y$k(B Hensel $B9=@.$K$h$j7W;;$5$l(B
        !           410: $B$k>l9g$,B?$$$,(B, $BA0=hM}$H$7$F(B, $B$$$/$D$+$N?t$"$k$$$O<0$rK!$H$7$F(B GCD $B$r(B
        !           411: $B7W;;$7$F$_$k$3$H$O(B, GCD $B$,(B 1 $B$G$"$k>l9g$N%A%'%C%/$H$7$FM-8z$G$"$k(B.
        !           412:
        !           413: $B:G8e$K(B, $B>jM>4D$G$NA|$+$i(B, $B5UA|$r5a$a$kJ}K!$r(B 2 $B$D>R2p$9$k(B.
        !           414: $B4D(B $R$ $B$O(B, $B@0?t4D$^$?$O(B, $BBN>e$N0lJQ?tB?9`<04D$H$7(B,
        !           415: $m_1, \cdots , m_r \in R$ $B$O8_$$$KAG$G$"$k$H$9$k(B. $B$3$N;~(B,
        !           416: $BM?$($i$l$?(B $u_1, \cdots, u_r \in R$ $B$KBP$7(B
        !           417: $$u \equiv u_i \pmod {m_i}$$
        !           418: $B$J$k(B  $u \in R$ $B$r5a$a$k$3$H$,L\I8$G$"$k(B.
        !           419: $m = \prod m_i$ $B$H$*$/(B.
        !           420:
        !           421: \begin{mt}(Lagrange $BJd4V(B)
        !           422: $\GCD(m_i,m/m_i)=1$ $B$h$j(B,
        !           423: $B$"$k(B $v_i, w_i \in R$ $B$,B8:_$7$F(B $v_i m/m_i + w_i m_i = 1.$
        !           424: $B$3$N;~(B
        !           425: $L_i = v_i m/m_i$ $B$H$*$1$P(B $L_i \equiv \delta_{ij} \pmod {m_j}$.
        !           426: $B$3$l$K$h$j(B,
        !           427: $u = \sum u_i L_i$ $B$H$*$1$P(B $u \equiv u_i \pmod {m_i}$.
        !           428: \end{mt}
        !           429: $B$3$l$O(B, $BK!$N?t$,8GDj$N;~(B, $B0lEY(B, $B4pDl(B $L_i$ $B$r7W;;$7$F$7$^$($P(B, $BG$0U$N(B
        !           430: $u_i$ $B$KBP$7$F@~7A7k9g$r:n$k$@$1$G2r$,F@$i$l$k$,(B, $BK!$N?t$,A}$($?;~$K(B
        !           431: $B4pDl$r7W;;$7D>$9I,MW$,$"$k(B.
        !           432:
        !           433: \begin{mt} (Newton $BJd4V(B)
        !           434: $i < j$ $B$N$H$-(B $\GCD(m_i,m_j)=1$ $B$h$j(B,
        !           435: $B$"$k(B $v_{ij}, N_{ij} \in R$ $B$,B8:_$7$F(B $v_{ij} m_j + N_{ij} m_i = 1.$
        !           436: $B$3$N;~(B
        !           437: $N_{ij} m_i \equiv 1 \pmod{m_j}, i < j.$
        !           438: $B$3$l$K$h$j(B
        !           439: $u = v_r m_{r-1}m_{r-2}+\cdots+v_2 m_1+v_1$
        !           440: $B$J$k7A$G(B $u$ $B$r5a$a$k$H(B
        !           441: \begin{tabbing}
        !           442: $v_1$ \= $=u_1$\\
        !           443: $v_j$ \>$= (\cdots((u_j-v_1)N_{1j}-v_2)N_{2j}-\cdots-v_{j-1})N_{j-1,j} \pmod{m_j})$\\
        !           444: $\cdots$
        !           445: \end{tabbing}
        !           446: \end{mt}
        !           447: $B$3$l$O(B, $m_1,\cdots,m_r$ $B$KBP$7$F9=@.$5$l$?2r$rMQ$$$F(B
        !           448: $m_1,\cdots,m_{r+1}$ $B$G$N2r$r7W;;$7$F$$$k(B. $B$=$N:](B, $B?7$?$KIU$12C$($?(B
        !           449: $m_{r+1}$ $B$rK!$H$9$k(B, $m_1,\cdots,m_r$ $B$N5U85$N7W;;$r9T$J$C$F$$$k(B.
        !           450: $v_j$ $B$N7W;;$,J#;($K8+$($k$,(B, $B<B:]$K$O(B, $j-1$ $B$KBP$9$k2r(B $u'$ $B$rMQ$$$F(B,
        !           451: $$(u_j-u')(m_1\cdots m_{j-1})^{-1} \bmod m_{j}$$$B$r7W;;$7$F$$$k$K2a$.$J(B
        !           452: $B$$(B. $B9=@.K!$+$i$o$+$k$h$&$K(B, $B$3$l$O(B, $BK!$N?t$rA}$d$7$F@:EY$r>e$2$F$$$/%?(B
        !           453: $B%$%W$N%"%k%4%j%:%`$K8~$/(B.
        !           454: