質問＜３１２５＞２００６／４／２５
from=えり
「ユークリッドの互除法」

次の問題がよくわかりません。教えてください。
・７２６１１，９１１４３の最大公約数を求めよ。
・これらの二数を素因数分解して上の結果が正しいことを
　確認せよ。

★希望★完全解答★

お便り２００６／４／２８
from=wakky

ユークリッドの互除法

　３｜７２６１１　　９１１４３｜１
　　｜５５５９６　　７２６１１｜
　　----------------------------
１１｜１７０１５　　１８５３２｜１
　　｜１６６８７　　１７０１５｜
    ----------------------------
　１｜　　３２８　　　１５１７｜４
　　｜　　２０５　　　１３１２｜
    ----------------------------
　１｜　　１２３　　　　２０５｜１
　　｜　　　８２　　　　１２３｜
    ----------------------------
　　｜　　　４１　　　　　８２｜２
　　｜　　　　　　　　　　８２｜
　　----------------------------
　　　　　　　　　　　　　　０

しががって、最大公約数は　４１

素因数分解すると
７２６１１＝７×１１×２３×４１
９１１４３＝３^2×１３×１９×４１

お便り２００６／４／２８
from=Luna

①91143,72611の最大公約数。

ユークリッドの互除法より
整数a,bに対し、aとbの最大公約数を(a,b)とすると
a=bq+rのとき(a,b)=(b,r)となるので、

これに基づいて
(91143,72611)
=(72611,18532)
=(18532,17015)
=(17015,1517)
=(1517,328)
=(328,205)
=(205,123)
=(123,82)
=(82,41)
=41
答え41

②素因数分解して確かめよ

91143=41×19×13×3^2
72611=41×23×11×7
よって最大公約数は41。以上証明完了。