輾轉相除法
附圖，長方形長34、寬10，用最少數的大小正方形鋪排而成。
34 ÷ 10 = 3...4 → 34 = 10 × 3 + 4
10 ÷ 4 = 2...2 → 10 = 4 × 2 + 2
4 ÷ 2 = 2...0 → 4 = 2 × 2
34=10×3+4=(4×2+2)×3+(2×2)=(2×12)+(2×3)+(2×2)=2×17。
10=4×2+2=(2×2)×2+2=(4+1)×2=5×2。
因為(17，5)=1，所以(10，34)=2。
因為2=10-(4×2)=10-(34-30)×2
=10-(34-3×10)×2
=10-34×2+3×10×2
=10×7+34×(-2)
所以 (10，34)=10×7+34×(-2)。
輾轉相除法
請輸入兩個自然數m和n
Copyright ©昌爸工作坊 all rights reserved.