package daniel.number_theory;

/**
 * 歐幾里德算法；輾轉(zhuǎn)相除法。
 * 
 * 如果 q 和 r 是 m 除以 n 的商及余數(shù),即 m=nq+r,
 * 如果 a 是m，n的最大公約數(shù)，所以m，n可以被a整除。又因?yàn)?有等是m=nq+r；所以a也可以整除r；
 * @author MIMO
 *
 */
public class LCD {
	
	public static int lcd(int a,int b){
		if(b == 0){
			return a;
		}
		return lcd(b,a % b);
	}
	
	public static void main(String [] args){
		System.out.println(lcd(11,20));
		System.out.println(10%20);
	}
}