[BACK]Return to gcd.tex CVS log [TXT][DIR] Up to [local] / OpenXM / doc / compalg

Annotation of OpenXM/doc/compalg/gcd.tex, Revision 1.1.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:

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>