# <center>輾轉相除法
**輾轉相除法是一種尋找兩數最大公因數的方法，也叫做歐幾里得演算法。以下是它的基本步驟：**

**給定兩個"正"整數a和b，並讓a >= b。
將a除以b取得商數和餘數 (a = bq + r)。
如果餘數r等於0，那麼b就是a和b的最大公因數。
如果餘數r不等於0，那麼讓a = b，b = r，並回到第二步繼續運算，直到找到最大公因數。**

## <center>證明
**假設d1 = (a , b)，d2 = (b , r)，求證d1 = d2。**
**因為d1是a和b的最大公因數，因此 d1|b，d1|a。("|"為整除的意思)**
**因此存在整数1和q滿足a = bq + r，得 r=a−bq=a×1−b×q 且 r為d1之倍數**
**也就是d1|(b,r)。所以d1|d2。**

**因為d2是b和r的最大公因數，所以 d2|b，d2|r。
因此同樣存在整數1和q。得 a=bq+r=b×q+r×1 所以d2|a(q為整數，且b跟a為d2之倍數)，
也就是d2|(a,b)，所以d2|d1。
而 d1|d2 且 d2|d1 ，在d1和d2都大於等於1(最大公因數)，因此d1 = d2，
即(a , b) = (b , r) 得證。**

## **題目練習**
**https://zerojudge.tw/ShowProblem?problemid=a024**
## **參考程式碼**

#include<bits/stdc++.h>
#define endl '\n'
#define IO cin.tie(0) -> sync_with_stdio(0)
using namespace std;

int gcd(int a , int b){
	int times = a/b;
	int r = a - b * times;
	if(r == 0) return b;
	else return gcd(b , r);
}

int main(){
	int a , b;
	while(cin >> a >> b){
		cout << gcd(a , b) << endl;
	}
}