ユークリッドの互除法（多項式）

3年の授業で時間が余ったので，いままで中学生相手にやっていた約分をやってみた．
＞以前の記事

高校3年なので，中学生には扱えなかった分数式の約分（多項式のGCM）もやってみた．


(1)
5184, 5832 のGCM 648
$648 = 2^3\cdot3^4$ なので，小さい数 2，3 で割れば約分できるという最も基本的なもの．
でも互除法なら 5832-5184 = 648 で両者を割れるから，一発で約分できる．

(2)
4752, 5616 のGCM 432
これも(1)同様 $432 = 2^4\cdot3^3$ だから順に割ればできる．
互除法の場合は， $5616 = 4752+864$，$4752 = 864\cdot5 + 432$，$846 = 432\cdot2$ より GCM がわかる．

(3)
$6109 = 41\cdot149$
$6407 = 43\cdot149$
なので，$2，3，5，7，11，\cdots$と順に割っていくと 13番目の 41，14番目の 43 で素因数分解できる．5秒に1回割り算しても3分以上かかることになる．
互除法の場合は，$6407-6109=298$，$6109=298\cdot20+149$，$298=149\cdot2$．
149で両者を割れることがわかるから，30秒とかからない．

(4)
$5781 = 3\cdot1927$
$6063 = 3\cdot2021$
まではすぐできるけど，1927，2021 の素因数がなかなか見つからず，あきらめてそれを答えにするかもしれない．
互除法なら $6063=5781+282$，$5781=282\cdot20+141$，$282=2\cdot141$ より共通因数 141 とわかり，
$5781 = 141\cdot41$
$6063 = 141\cdot43$
これも，順に割れば3分以上かかることになる．

(5)
$19872=12528+7344$, $12528=7344+5184$，$7344=5184+2160$
$5184=2160\cdot2+864$，$2160=864\cdot2+432$，$864=432\cdot2$
共通因数 432 で割れて，
$12528 = 432\cdot29$
$19872 = 432\cdot46$
432 の素因数は 2, 3の累乗しかないから，これは見つからないということはないが時間はかかる．

(6)
$62884891=62821427+63464$
$62821427=63464\cdot989+55531$
$63464=55531+7933$
$55531=7933\cdot7$
共通因数 7933 で割れて，
$62821427=7933\cdot7919$
$62884891=7933\cdot7927$
7919は1000番目の素数，7927は1001番目の素数，7933は1002番目の素数だから，
素因数分解しようと5秒に1回割り算しても，5000秒=1時間23分かかる．


(7)
$x^2−3x+2 = (x-2)(x-1)$
$x^2−5x+6 = (x-2)(x-3)$
は中学生でもできる．
互除法では，
$(x^2−3x+2)-(x^2−5x+6) = 2x-4 =2(x-2)$
$x-2$ で両者を割れるから約分できるが，この程度では有り難みはない．

ここで，多項式の因数分解では定数倍して同じものは同じと因数とみなすことに注意．
つまり
$(x-2)(x-1) = (-x+2)(-x+1) = (5x-10)\left(\frac{x}{5} - \frac{1}{5}\right)$
であるから，互除法ではテキトーに定数倍して次数の高い項を消していく作業になる．

(8)
これはとりあえず，数学II で習う因数定理で因数分解できる．
$P(x)=x^3−2x+1$ のとき $P(1)=0$ より，$x-1$ を因数に持ち，割ると $x^2+x-1$ も因数．
$Q(x)=x^3+3x^2+x−2$ のとき，$Q(-2)=0$ より $x+2$ を因数に持ち，割ると $x^2+x-1$ も因数．
$x^3−2x+1 = (x-1)(x^2+x-1)$
$x^3+3x^2+x−2 = (x+2)(x^2+x-1)$
互除法では，
$(x^3-2x+1) - (x^3+3x^2+x-2) = -3x^2-3x+3 = -3(x^2+x-1)$
$(x^3+3x^2+x−2)-x(x^2+x-1) = 2x^2+2x-2 = 2(x^2+x-1)$
より共通因数 $x^2+x-1$

(9)
$(x^4+2x^3+x^2-1) - (x^4+3x^3+x^2-2) = x^3-1$
$(x^4+3x^3+x^2-2) - x(x^3-1) = 3x^3+x^2+x-2$
$3x^3-3 - (3x^3+x^2+x-2) = -x^2-x-1 = -(x^2+x+1)$
$3x^3+x^2+x-2 - 3x(x^2+x+1) = -2(x^2+x+1)$
より共通因数 $x^2+x+1$
$x^4+2x^3+x^2-1 = (x^2+x+1)(x^2+x-1)$
$x^4+3x^3+x^2-2 = (x^2+x+1)(x^2+2x-2)$

これらの根にはすべて√や虚数が出るから，因数定理での因数分解は不可能．
「因数分解せずに約分」が互除法のパワーである．
ユークリッドの互除法は人類が最初に発見したアルゴリズムということらしい．（書物に記された最初はユークリッドの「原論」らしいが，もちろんそれ以前に知られていたに違いない．）

(10) (9)と同様．

＞くろべえ「互除法」関連の記事