輾轉相除法意思

輾轉相除法（也稱為歐幾里得算法或Euclidean algorithm）是一種計算兩個整數最大公約數（ Greatest Common Divisor, GCD）的算法。這個算法是由古希臘數學家歐幾里得在他的著作《幾何原本》中提出的，因此得名。

輾轉相除法的原理是通過不斷地用較大的數除以較小的數，直到商為1為止。此時，所得的餘數就是兩個數的最大公約數。以下是一個簡單的例子：

例如，我們要找出50和24的最大公約數。

1. 首先，用較大的數50除以較小的數24，得到商為2，餘數為14。 50 ÷ 24 = 2...14

2. 接著，用上一個除數24除以餘數14，得到商為1，餘數為8。 24 ÷ 14 = 1...10

3. 繼續用上一個餘數14除以這個餘數10，得到商為1，餘數為4。 14 ÷ 10 = 1...4

4. 重複上述過程，直到餘數為0為止。 10 ÷ 4 = 2...2 4 ÷ 2 = 2...0

5. 當餘數為0時，我們停止計算，最後一個非零的餘數就是兩個數的最大公約數。

在這個例子中，最後一個非零的餘數是2，所以50和24的最大公約數是2。

輾轉相除法不僅可以用來計算兩個數的最大公約數，還可以用來檢查一個數是否是另一個數的因數，以及將一個數分解質因數等。