Return to gcd.tex CVS log

Up to [local] / OpenXM / doc / compalg

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

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