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>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to gcd.tex CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM / doc / compalg