更相減損法如何計算大整數最大公約數

更相減損法是一種基於試除法（又稱輾除法）的算法，用於求兩個數的最大公約數。在更相減損法中，我們通過不斷地將兩個數中的較大數除以較小數，並將這個除法的餘數加入到新的數列中，直到兩個數中的較小數變為0為止。此時，最大公約數就是最初被減去的那個數。

以下是使用更相減損法求大整數的最大公約數的步驟：

1. 將兩個數中的較大數除以較小數，得到第一個除法結果。
2. 將這個除法的餘數加入到新的數列中。
3. 將新的數列中的兩個數中的較大數除以較小數，得到第二個除法結果。
4. 重複步驟2和3，直到新的數列中只剩下一個數（即餘數為0）。
5. 這個數為最大公約數。

需要注意的是，這種方法只適用於大整數之間的最大公約數的計算，對於小整數之間的最大公約數，通常使用更簡單的歐幾里得算法（輾除法）即可。

以下是一個Python代碼示例，用於使用更相減損法求大整數的最大公約數：

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

這個函式接受兩個整數作為參數，並返回它們的最大公約數。在循環中，每次疊代都會將較小的數替換為較大的數與餘數的差值，直到較小的數為0為止。最終得到的結果就是最大公約數。