ユークリッドの互除法

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

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

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

①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。以上証明完了。