$BCf9q?M>jM>DjM}(B (Chinese remainder theorem)


$BO"N)#1 xb1 (mod d1 )
xb2 (mod d2 )
$B!D(B
xbt (mod dt )
$B$N>l9g!"(B d1, d2, $B!D(B dt $B$,8_$$$KAG$G$"$l$P!"(B
n = d1 d2 $B!D(B dt
$B$rK!$H$7$F!"$?$@0l$D$N2r$,$"$k!#(B
$B$^$:!"(Bn / di = ni $B$H$*$1$P!"(B di $B$H(B ni $B$O8_$$$KAG$G$"$k$+$i!"(B
ni xi $B-q(B 1 (mod di )
$B$N2r(B xi $B$r5a$a$k$3$H$,$G$-$k!#$=$3$G!"(B
xb1 n1 x1 + b2 n2 x2 + $B!D(B + bt nt xt (mod n)
$B$H$9$l$P!"$3$N(B x $B$OL@$i$+$K$b$H$N9gF1<0$r$9$Y$FK~B-$9$k!#(B

$B$3$N$h$&$JO"N)9gF1<0$N@-$BCf9q?M>jM>DjM}(B (Chinese remainder theorem) $B$H8F$V!#(B


SEE ALSO


www.finetune.co.jp [Mail] © 2000 Takayuki HOSODA.
Powered by
 Finetune