题解 | #最大公约数#

核心：gcb(a, b) = gcb(b, a%b)
证明：只要证明gcb(a, b) = gcb(b, a-b)即可
假设gcb(a, b) = c，证明分两步：

• step 1：证明c是gcb(b, a-b)的公约数
  gcb(a,b) = c
  => a = k1*c, b = k2*c
  => a-b = (k1-k2)*c, 又b=k2*c
  => c是b和a-b的公约数
• step 2：证明c是gcb(b, a-b)的最大公约数
  假设存在d>c且b=k3*d, a-b=k4*d
  => a = (k4-k3)*d, b = k3*d
  => 与c是a,b的最大公约数矛盾
  => c是b, a-b的最大公约数

  #
  # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
  #
  # 求出a、b的最大公约数。
  # @param a int 
  # @param b int 
  # @return int
  #
  class Solution:
    def gcd(self , a , b ):
        # write code here
        if a%b == 0:
            return b 
        else:
            return self.gcd(b, a%b)
  

```