✔ 最佳答案
先初步分解 ,盡量抽出較明顯的因數以簡化問題。
注意 2+0+1+3+0+3+0+3 = 12 可被 3 整除 ,
得 20130303 = 3 x 6710101。 注意 1-2+3-4+5-6+7-4 = 0 可被 11 整除, 又 12345674 可被 2 整除 ,
得 12345674 = 2 x 11 x 561167。問題轉為求 6710101 和 561167 的最大公因數。
它們沒有明顯的因數 , 故可利用輾轉相除法 :6710101 = 561167 x 12 - 23903
561167 = 23903 x 23 + 11398
23903 = 11398 x 2 + 1107
(注意到 3 x 3 x 3 x 41 = 1107 , 局勢已明朗 , 41 即為答案 , 下面步驟可省略 )
11398 = 1107 x 10 + 328
1107 = 328 x 3 + 123
328 = 123 x 2 + 82
123 = 82 + 41
82 = 41 x 2 + 0得 20130303 和 12345674 的最大公因數是 41 。