Return to gcd.tex CVS log

Up to [local] / OpenXM / doc / compalg

Added $OpenXM$.

%$OpenXM: OpenXM/doc/compalg/gcd.tex,v 1.2 2000/03/28 02:02:30 noro Exp $
\chapter{$BB?9`<0$N(B GCD}
\section{Euclid $B$N8_=|K!(B}
$R$ $B$r(B UFD (Unique Factorization Domain; $B0l0UJ,2r@00h(B) $B$H$7(B, $R$ $B$K$*(B
$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
$B$b(B GCD $B$N7W;;$,2DG=$H$J$k(B. $R$ $B$N>&BN$r(B $Q(R)$ $B$H=q$/(B.
\begin{df}
$$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. 
\end{df}

\begin{pr}
$\pp(f)$ $B$O86;OE*(B. 
\end{pr}
\proof
$G=\GCD(a_0,\cdots,a_n),L=\LCM(b_0,\cdots,b_n)$
$B$H=q$/(B.
$\pp(f)=\sum_i L/b_i\cdot a_i/G\cdot x^i$ $B$h$j(B,
$\cont(\pp(f)) = \GCD(L/b_0\cdot a_0/G, \cdots) \in R.$
 $BAG85(B $p$ $B$,1&JU$r3d$k$H$9$k(B. $B$b(B
$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
$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 
$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,
$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, 
$p|(L/b_i)$ $B$3$l$OIT2DG=(B. $B$h$C$F(B $\cont(\pp(f)) = 1$. \qed

\begin{lm}[Gauss]
$f,g \in Q(R)[x]$ $B$KBP$7(B, $\cont(fg) = \cont(f)\cont(g).$
\end{lm}

\begin{pr}
$f, g \in R[x]$ $B$KBP$7(B,
$\GCD(f,g) = \GCD(\cont(f),\cont(g))\GCD(\pp(f),\pp(g))$
$B$^$?(B, $f, g \in R[x]$ $B$r86;OB?9`<0$H$9$k$H(B, 
$\GCD(f,g) = \pp(\GCD_{Q(R)}(f,g))$
$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
GCD $B$r0UL#$9$k(B. 
\end{pr}

$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
GCD $B$K$h$j7W;;$G$-$k$3$H$,$o$+$C$?(B. $B$7$+$7(B, $B<B:]$K>&BN$G$N1i;;$r(B
$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, 
$BB?9`<0$N=|;;$G(B, $B>&BN$N=|;;$,8=$l$J$$$b$N$r9M$($k(B. 

\begin{df}
$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
(pseudo-remainder) $\prem(f,g)$ $B$r(B
$$\prem(f,g) = {\rm remainder}(\lc(g)^{\deg(f)-\deg(g)+1}f,g)$$
$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. 
\end{df}

$BMF0W$K$o$+$k$h$&$K(B, $\prem(f,g)$ $B$N7W;;$NESCf$K8=$l$k=|;;$O(B, 
$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
$B<!$N$h$&$K$J$k(B. 

\begin{al}
\label{euclid}
\begin{tabbing}
\\
Input : $B86;OE*B?9`<0(B $f_1, f_2 \in R[x]$, $\deg(f_1) \ge \deg(f_2)$\\
Output : $\GCD(f_1,f_2)$\\
$i \leftarrow 1$\\
do \= \{\\
\> $f_{i+2} \leftarrow \prem(f_i,f_{i+1})$\\
\> if \= ( $f_{i+2} = 0$ ) then return $\pp(f_{i+1})$\\
\> $i \leftarrow i+1$\\
\}
\end{tabbing}
\end{al}

\begin{df}
$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
$B;;$K$h$j@8@.$5$l$kNs(B $\{f_i\}$ $B$rB?9`<0>jM>Ns$H8F$V(B.
\end{df}

\section{$B3HD%(B Euclid $B8_=|K!(B}
$BBN(B $K$ $B>e$N0lJQ?tB?9`<04D(B $K[x]$ $B$O(B PID (Principal Ideal Domain; $BC19`(B
$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 
$(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
$B$7$F(B,
$$af+bg=\GCD(f,g)$$ $B$H=q$1$k(B. $B$3$N78?t(B $a, b$
$B$O(B, Euclid $B$N8_=|K!$NJQ7A$K$h$j5a$a$k$3$H$,$G$-$k(B. 

\begin{al}
\begin{tabbing}
\\
Input : $B86;OE*B?9`<0(B $f_1, f_2 \in K[x]$, $\deg(f_1) \ge \deg(f_2)$\\
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]$\\
$a_1 \leftarrow 1$, $a_2 \leftarrow 0$, $b_1 \leftarrow 0$, $b_2 \leftarrow 1$\\
$i \leftarrow 1$\\
do \= \{\\
\> $\deg(f_i - q_i f_{i+1}) < \deg(f_{i+1})$ $B$J$k(B $q_i$ $B$r5a$a$k(B\\
\> $f_{i+2} \leftarrow f_i - q f_{i+1}$;
\quad $a_{i+2} \leftarrow a_i - q a_{i+1}$;
\quad $b_{i+2} \leftarrow b_i - q b_{i+1}$\\
\> if \= ( $f_{i+2} = 0$ ) then return $\{f_{i+1},a_{i+1},b_{i+1}\}$\\
\> $i \leftarrow i+1$\\
\}
\end{tabbing}
\end{al}
$B$3$3$G8=$l$?(B $a_i, b_i$ $B$KBP$7(B, 
$$\deg(a_i) \le \deg(f_2)-\deg(f_{i-1}),\quad \deg(b_i) \le \deg(f_1)-\deg(f_{i-1})$$
$B$G$"$k$3$H$o$+$k(B. 
$BFC$K(B, $f = f_i = \GCD(f_1,f_2)$ $B$J$i$P(B 
$$\deg(a_i) < \deg(f_2)-\deg(f), \quad \deg(b_i) < \deg(f_1)-\deg(f).$$

\begin{pr}
$f, g \in K[x]$ $B$KBP$7(B, $h = \GCD(f,g)$ $B$H$9$k$H(B, 
$af+bg=\GCD(f,g)$ $B$+$D(B $\deg(a) < \deg(g) - \deg(h),\quad \deg(b) < \deg(f) - \deg(h)$
$B$J$k(B $a, b \in K[x]$ $B$OB8:_$7$F0l0UE*(B. 
\end{pr}
\proof
$B0l0U@-$N$_<($;$P$h$$(B. $h$ $B$GN>JU$r3d$C$F(B, $h=1$ $B$H$7$F$h$$(B. 
$$af+bh=1, \quad a_1f+b_1g=1,$$
$$\deg(a)<\deg(g),\quad \deg(b)<\deg(f),\quad \deg(a_1)<\deg(g),\quad \deg(b_1)<\deg(f)$$
$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
$g|(a-a_1).$
$\deg(a-a_1)<\deg(g)$ $B$h$j(B $a-a_1=b-b_1=0.$\qed\\
$af+bg=1$ $B$J$i$P(B $af \equiv 1 \bmod g$
$B$9$J$o$A(B, $B>jM>4D(B $K[x]/(g)$ $B$K$*$$$F(B
$a \bmod g = (f \bmod g)^{-1}$
$B$G$"$k(B. 
$B>jM>4D$K$*$1$k5U857W;;$O(B, $B7W;;5!Be?t$K$*$$$FIQHK$KI,MW$H$J$j(B, 
$BFC$K8e$G=R$Y$k(B modular $B%"%k%4%j%:%`$K$*$$$F6K$a$F=EMW$JLr3d$r1i$:$k(B.

$B$3$NL?Bj$O(B, $B<!$N$h$&$K0lHL2=$G$-$k(B.

\begin{pr}
$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. 
$B$3$N$H$-(B, 
$$\sum_{i=1}^n e_i (f/f_i) =1, \quad \deg(e_i)<\deg(f_i)$$
$B$J$k(B $e_i \in K[x]$ $B$,0l0UE*$KB8:_$9$k(B. 
\end{pr}
\proof $B5"G<K!$K$h$j(B, 
$\sum_{i=1}^n E_i (f/f_i) =1$
$B$J$k(B $E_i$ $B$,B8:_$9$k$3$H$,J,$+$k(B. $E_i = q_if_i+e_i$ 
($\deg(e_i)<\deg(f_i)$) $B$H=|;;$r9T$&$H(B, 
$$f\sum_{i=1}^n{q_i}+\sum_{i=1}^n e_i(f/f_i)=1.$$
$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$
$B$,@.$jN)$D$+$i(B, 
$$\sum_{i=1}^n e_i (f/f_i) =1, \quad \deg(e_i)<\deg(f_i).$$
$B$3$N$h$&$J(B $e_i$ $B$O(B $\bmod f_i$ $B$G0l0UE*$@$+$i(B, $\deg(e_i)<\deg(f_i)$
$B$G$O0l0U$K7h$^$k(B. 
\qed

\begin{pr}
\label{exteuc}
$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. 
$\deg(g)\le \deg(f)$ $B$J$i$P(B,
$$\sum_{i=1}^n e_i (f/f_i) =g \quad \deg(e_i)\le \deg(f_i)$$
$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, 
$\deg(e_i)< \deg(f_i)$ $B$H$G$-$F(B, $e_i$ $B$O0l0UE*(B.
\end{pr}
\proof
$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. 
$E_i = q_if_i+e_i$ ($\deg(e_i)<\deg(f_i)$) $B$H=|;;$r9T$&$H(B, 
$$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,
 \quad c = \sum_{i=1}^n q_i$$
$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
$\deg(cf)\le \deg(f)$ $B$9$J$o$A(B
$\deg(c)\le 0.$ $B$h$C$F(B
$\deg(e_1+cf_1) \le \deg(f_1).$
$BFC$K(B, $\deg(g)<\deg(f)$ $B$J$i$P(B $c=0$ $B$h$j(B
$\deg(e_1+cf_1) = \deg(e_1) < \deg(f_1).$
$B0l0U@-$bA0L?Bj$HF1MM(B. 
\qed

\begin{co}
({\bf $BItJ,J,?tJ,2r(B})
\label{parfrac}

$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, 
$r_{ij} \in K[x]$ ($1\le j \le i, \deg(r_{ij}) < \deg(d_i)$) $B$,B8:_$7$F(B, 
$$n/d = \sum_{i=1}^n \sum_{j=1}^i r_{ij}/d_i^j.$$
\end{co}
\proof
$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
$BB8:_$7$F(B
$n = \sum_{i=1}^n E_i(d/D_i).$
$B$3$l$+$i(B
$n/d=\sum_{i=1}^n E_i/d_i^i.$
$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
$E_i=\sum_{j=1}^i r_{ij}d_i^{(i-j)},$ $\deg(r_{ij})<\deg(d_i)$
$B$H=q$1$k(B. $B$h$C$F(B
$E_i/d_i^i = \sum_{j=1}^i r_{ij}/d_i^j.$
\qed

\section{$B=*7k<0(B}
$R$ $B$r2D494D$H$9$k(B. 
\begin{df}
$$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)$$
$B$KBP$7(B, $a,b$ $B$N(B Sylvester $B9TNs(B $Syl(a,b)$ $B$r<!$GDj5A$9$k(B. 

\[ Syl(a,b) = \left[
\begin{array}{cccccc}
a_n & a_{n-1} & \cdots & a_0 & & \\
    & \cdots  & \cdots & \cdots & \cdots &  \\
    &         & a_n    & a_{n-1} & \cdots & a_0   \\
b_m & b_{m-1} & \cdots & b_0 & & \\
    & \cdots  & \cdots & \cdots & \cdots &  \\
    &         & b_m    & b_{m-1} & \cdots & b_0   \\
\end{array}
\right]
\]

$a,b$ $B$N=*7k<0(B $\res_x(a,b)$ $B$r(B $\res_x(a,b)=\det(Syl(a,b))$
$B$GDj5A$9$k(B. 
\end{df}

\begin{lm}
$\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$

$\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
\begin{equation}
\label{syleq}
[s_{m-1},\cdots, s_1, s_0, t_{n-1}\,\cdots,t_1, t_0] Syl(a,b) = [0,\cdots,0]
\end{equation}
\end{lm}

\begin{co}
$R$ $B$,@00h$H$9$k(B. 
$\deg(s)<\deg(b), \deg(t)<\deg(a)$ $B$J$k(B $s,t \in R[x]\setminus \{0\}$
$B$,B8:_$7$F(B $sa+tb=0 \Leftrightarrow \res_x(a,b)=0$
\end{co}

\begin{pr}
$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
$BBP$7(B, 
$$\deg(\GCD(a,b))>0 \Leftrightarrow \res_x(a,b) = 0.$$
\end{pr}
\underline{$\Rightarrow$}\\
$g=\GCD(a,b)$, $\deg(g)>0$ $B$H$9$k$H(B, $(b/g)\cdot a + (a/g)\cdot b=0.$
$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
$\res_x(a,b)=0$. \\
\underline{$\Leftarrow$}\\
$\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. 
$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.$
$\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
$\GCD(a,b)$ $B$ODj?t$G$J$$(B.\qed

\section{$BItJ,=*7k<0(B}
$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.
$B<!$NNc$r9M$($F$_$k(B. 

\begin{ex}
$$R = \Z,\quad f = x^8+x^5+1,\quad g = 3x^6+1$$
$B$3$N>l9g(B, $BESCf$G@8@.$5$l$k5<>jM>$O(B,
\begin{center}
$27x^5-9x^2+27$\\
$729x^3-2187x+729$\\
$-13947137604x^2+94143178827x-20920706406$\\
$5822950344611693220025353x-1293988965469265160005634$\\
$-23353191009282740851191794693386216142000386817007672113424$
\end{center}
$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
$BA}$($F$$$k$3$H$,J,$+$k(B. 
\end{ex}
$B<B:]$K$O(B, $B>e$NNc$G$O(B, $BESCf$G@8@.$5$l$k5<>jM>$O86;OE*$G$J$/(B, 
$BMFNL$r=|$/$H<!$N$h$&$K$J$k(B. 
\begin{center}
$3x^5-x^2+3$\\
$x^3-3x+1$\\
$-4x^2+27x-6$\\
$9x-2$\\
$-1$
\end{center}

$B$3$N>l9g(B, $B5<>jM>$NMFNL$r<B:]$K(B GCD $B$rMQ$$$F7W;;$7$?$,(B, $B<B$O$"$kDxEY$N(B
$BItJ,$O(B, $B<+F0E*$K<h$j=|$/$3$H$,$G$-$k(B. $B$3$N$?$a(B, $BItJ,=*7k<0(B  (subresultant)
$B$rF3F~$9$k(B. 

\begin{df}
$\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, 
$f,g$ $B$N(B $j$ $B<!$NItJ,=*7k<0(B $S_j(f,g)$ $B$r<!$N9TNs<0$GDj5A$9$k(B. 

\[ S_j(f,g) = \left|
\begin{array}{cccccc}
a_n & a_{n-1} & \cdots & \cdots & \cdots & x^{m-j-1}f \\
    & \cdots  & \cdots & \cdots & \cdots & \cdots \\
    &         & a_n    & \cdots & a_{j+1}& f   \\
b_m & b_{m-1} & \cdots & \cdots & \cdots & x^{n-j-1}g \\
    & \cdots  & \cdots & \cdots & \cdots & \cdots \\
    &         & b_m    & \cdots & b_{j+1}& g   \\
\end{array}
\right|
\]
$BFC$K(B, $S_0(f,g) = \res_x(f,g)$ ($B=*7k<0(B) $B$H$J$k(B. 
\end{df}

\begin{df}
$f \sim g$ $B$H$O(B $\pp(f) = \pp(g)$ $B$J$k$3$H(B. 
\end{df}

\begin{pr}
{\rm \cite{SUB}}
$\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
$\{f_1, f_2, \cdots\}$ $B$KBP$7(B, 
$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}.$
\end{pr}

$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
$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
$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
$B<B:]$K2DG=$G$"$k(B.

\begin{pr}
$BB?9`<0>jM>Ns$r(B, 
$$d_i = \deg(f_i)-\deg(f_{i+1}),\quad \alpha_i = 1,$$
$$\beta_2 = 1,\quad \beta_i = \lc(f_{i-1})\zeta_i^{d_{i-1}},$$
$$\zeta_2 = 1,\quad \zeta_i = \lc(f_{i-1})^{d_{i-2}}\zeta_{i-1}^{(1-d_{i-2})},$$
$$f_{i+1} = \prem(f_{i-1},f_i)/\beta_i$$
$B$GDj$a$l$P(B, 
$$f_i = \pm S_{\deg(f_{i-1})-1}(f_1,f_2).$$
\end{pr}

$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
$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
$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
$B$$$k$H9M$($i$l$k(B. $B<B:]$K(B, $BA0$NNc$KE,MQ$7$F$_$k$H(B, \\
\begin{center}
$27x^5-9x^2+27$\\
$27x^3-81x+27$\\
$-36x^2+243x-54$\\
$1971x-438$\\
$-5329$
\end{center}
$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
$B$3$H$,$o$+$k(B. 

\section{Modular $B%"%k%4%j%:%`(B}
$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
$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
$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
$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. 
modular $B%"%k%4%j%:%`$H$O(B, $B78?t4D$N>jM>4D$K$*$1$k1i;;7k2L$+$i$b$H$N(B
$B4D>e$N7k2L$rF@$k%?%$%W$N%"%k%4%j%:%`$NAm>N$G$"$k(B. modular $B%"%k%4%j%:%`(B
$B$K$O(B, $BCf9q>jM>DjM}$rMQ$$$k$b$N$H(B, Hensel $B9=@.$rMQ$$$k$b$N$,$"$k(B. 
$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
$B$D$$$F=R$Y$k(B. 

\begin{pr}($BCf9q>jM>DjM}(B)
$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
$BBP$7(B,$A_i+A_j=A$ $B$J$i$P(B,
$$\quad  A/\prod A_i \simeq \bigoplus A/A_i.$$
\end{pr}
\proof
 $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 
$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
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, 
$BI8=`E*<LA|(B 
$$\phi : A \rightarrow A/A_1 \oplus A/A_2$$
$B$OA4<M$+$D(B
$\Ker(\phi) = A_1\cap A_2$ $B$h$j(B 
$A/A_1\cap A_2 \simeq A/A_1 \oplus A/A_2.$
$B$3$3$G(B, 
$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$
$B$h$j(B, $A_1 A_2 = A_1\cap A_2.$
$B$h$C$F(B 
$$A/A_1 A_2 \simeq A/A_1 \oplus A/A_2.$$
$B0lHL$N>l9g$O(B, $A_1+A_2\cdots A_r \supset \prod_{i\ge 2}(A_1+A_i) \ni 1$
$B$h$j5"G<K!$,;H$($k(B. \qed

\begin{co}
$A$ $B$r(B Euclid $B4D$H$9$k(B. $m_i \in A$ $B$,8_$$$KAG$J$i$P(B, 
$A/(\prod m_i) \simeq \bigoplus A/(m_i)$.
\end{co}

\begin{ex}
$K$ $B$rBN$H$9$k(B. $f_i \in K[x]$ $B$,8_$$$KAG$J$i$P(B, 
$K[x]/(\prod f_i) \simeq \bigoplus K[x]/(f_i)$.
\end{ex}

$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
$x-a_i$ $B$J$k7A$N$b$N$r$H$l$P(B, $BJd4VK!$r$"$i$o$9$H9M$($i$l$k(B. 

\begin{ex}
$m_i \in \Z$ $B$,8_$$$KAG$J$i$P(B, 
$\Z/(\prod m_i) \simeq \bigoplus \Z/(m_i)$.
\end{ex}

$B<!$NJdBj$O(B, modular $B1i;;$K$h$k%$%a!<%8$r$b$H$N6u4V$K0z$-La$9:]$K(B
$B>o$KMQ$$$i$l$k(B. 

\begin{lm}
$a \equiv a' \bmod A$, $|a| \le B$, $|a'| \le A/2$, $A > 2B$ $B$J$i$P(B, 
$a = a'$.
\end{lm}
\proof
$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

\vskip \baselineskip
$BCf9q>jM>DjM}$N1~MQ$H$7$F(B, $\Z[x]$ $B$K$*$1$k(B GCD $B7W;;$rNc$K$H$k(B. 
$$f, g \in \Z[x],\quad h = \GCD(f,g) \in \Z[x]$$
$B$H$9$k(B. $B$3$N;~(B, 
$$\GCD(f \bmod p_i,g \bmod p_i) = h \bmod p_i$$
$B$J$kAG?t(B $p_i$ $B$,M?$($i$l$l$P(B, $B78?t$KBP$7$FCf9q>jM>DjM}(B
$B$rE,MQ$7$F(B, 
$$m=\prod p_i | (h - h_1)$$
$B$J$k(B $h_1$ $B$r9=@.$G$-$k(B. $B$3$3$G(B,
$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 
$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. 
$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, 
$B$9$J$o$ABEEv$G$"$k$+$I$&$+ITL@$G$"$k$H$$$&E@$G$"$k$,(B, $BBEEv$G$J$$(B $p$ 
$B$OM-8B8D$7$+$J$$$3$H$,$o$+$k(B ($B8_$$$KAG$J>l9g$N=*7k<0$r9M$($l$P$h$$(B). 
$p$ $B$NBEEv@-$OK!(B $p$ $B$G$N(B GCD $B$N<!?t$,:GDc$H$$$&>r7o$GFCD'$E$1$i$l$k$?(B
$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.

$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
$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
$B$7$F(B, $BESCf$N7W;;$K$*$$$FBg$-$J<0$,8=$l$k>l9g(B ($BCf4V<0KDD%(B)$B$G$"$k(B.  $B8=:_(B
$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
$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
$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. 

$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. 
$B4D(B $R$ $B$O(B, $B@0?t4D$^$?$O(B, $BBN>e$N0lJQ?tB?9`<04D$H$7(B, 
$m_1, \cdots , m_r \in R$ $B$O8_$$$KAG$G$"$k$H$9$k(B. $B$3$N;~(B, 
$BM?$($i$l$?(B $u_1, \cdots, u_r \in R$ $B$KBP$7(B
$$u \equiv u_i \pmod {m_i}$$
$B$J$k(B  $u \in R$ $B$r5a$a$k$3$H$,L\I8$G$"$k(B. 
$m = \prod m_i$ $B$H$*$/(B. 

\begin{mt}(Lagrange $BJd4V(B)
$\GCD(m_i,m/m_i)=1$ $B$h$j(B, 
$B$"$k(B $v_i, w_i \in R$ $B$,B8:_$7$F(B $v_i m/m_i + w_i m_i = 1.$
$B$3$N;~(B 
$L_i = v_i m/m_i$ $B$H$*$1$P(B $L_i \equiv \delta_{ij} \pmod {m_j}$.
$B$3$l$K$h$j(B, 
$u = \sum u_i L_i$ $B$H$*$1$P(B $u \equiv u_i \pmod {m_i}$.
\end{mt}
$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
$u_i$ $B$KBP$7$F@~7A7k9g$r:n$k$@$1$G2r$,F@$i$l$k$,(B, $BK!$N?t$,A}$($?;~$K(B
$B4pDl$r7W;;$7D>$9I,MW$,$"$k(B.

\begin{mt} (Newton $BJd4V(B)
$i < j$ $B$N$H$-(B $\GCD(m_i,m_j)=1$ $B$h$j(B, 
$B$"$k(B $v_{ij}, N_{ij} \in R$ $B$,B8:_$7$F(B $v_{ij} m_j + N_{ij} m_i = 1.$
$B$3$N;~(B 
$N_{ij} m_i \equiv 1 \pmod{m_j}, i < j.$
$B$3$l$K$h$j(B
$u = v_r m_{r-1}m_{r-2}+\cdots+v_2 m_1+v_1$
$B$J$k7A$G(B $u$ $B$r5a$a$k$H(B 
\begin{tabbing}
$v_1$ \= $=u_1$\\
$v_j$ \>$= (\cdots((u_j-v_1)N_{1j}-v_2)N_{2j}-\cdots-v_{j-1})N_{j-1,j} \pmod{m_j})$\\
$\cdots$
\end{tabbing}
\end{mt}
$B$3$l$O(B, $m_1,\cdots,m_r$ $B$KBP$7$F9=@.$5$l$?2r$rMQ$$$F(B 
$m_1,\cdots,m_{r+1}$ $B$G$N2r$r7W;;$7$F$$$k(B. $B$=$N:](B, $B?7$?$KIU$12C$($?(B
$m_{r+1}$ $B$rK!$H$9$k(B, $m_1,\cdots,m_r$ $B$N5U85$N7W;;$r9T$J$C$F$$$k(B. 
$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,
$$(u_j-u')(m_1\cdots m_{j-1})^{-1} \bmod m_{j}$$$B$r7W;;$7$F$$$k$K2a$.$J(B
$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
$B%$%W$N%"%k%4%j%:%`$K8~$/(B.