首先先說，歐幾裡德一共有倆，歐幾裡德和擴充歐幾裡德，前者非常簡單，後者直接變态（因為我太菜）
gcd = 最大公因數
普通歐幾裡德
先說普通的，就是輾轉相除法求最大公因數，輾轉相除就是基本數論，不講了直接上代碼
View Code
遞歸終止的邊界就是a是b的倍數，也就是 a%b == 0
其中保證b一定是小于a的，也就是說一直是b $\le$ a ，是以判斷b是否為0就好了
擴充歐幾裡德
然後就到了一個變态的東西了
先引入一個東西，叫裴蜀定理
搞定了裴蜀定理，下面就能證了：
我們這裡有兩個數，a,b $\in$ N 且 a,b互質。
對于a，b來說，一定存在 x,y $\in$ N滿足；
ax + by = 1 = gcd( a,b )
已知gcd( a,b ) = gcd( b,a%b )
且因為a,b互質，則 gcd( b,a%b ) 的值一定也為 1，
是以也一定存在 bx' + ( a - b$\lfloor \frac{a}{b} \rfloor$ )y' = 1