最大公約數(簡寫為gcd)是指能同時除兩個或兩個以上給定整數的最大正整數。
求最大公約數是數論中的壹個基本問題，廣泛應用於計算機科學、信息學、密碼學等領域。求兩個整數m和n的最大公約數的方法有很多，下面是兩種常用的方法:
1，輾轉減法:輾轉減法是古希臘數學家歐幾裏得提出的壹種求最大公約數的方法。具體操作如下:
首先比較M和N的大小，將較大的賦給A，較小的賦給B；計算a和b的差，賦給t；如果t等於0，那麽b就是最大公約數；如果t不等於0，用(a，t)代替原來的(a，b)，然後重復2~4步，直到t等於0。折騰減法的時間復雜度為O (n 2)，在處理大數時效率很低。
2.換相除法:換相除法是壹種基於歐幾裏德定理推論的求最大公約數的算法，也稱為歐幾裏德算法。歐幾裏德算法的核心思想是利用余數的遞歸使原問題不斷約化，原問題的解等價於約化問題的解。具體操作如下:
比較m和n，用較大的數除以較小的數，得到商q和余數r；如果r等於0，較小的數就是最大公約數；
如果r不等於0，用較小的數和余數r繼續進行上述運算，直到余數為0，此時較小的數為最大公約數。相除的時間復雜度為O(log n)，在處理大數時效率較高。
綜上所述，可以用兩種方法求兩個整數m和n的最大公約數，即折騰減法和折騰除法。但需要註意的是，這兩種方法計算極大數的時間可能會比較長，所以通常需要更高效的算法來解決這個問題。