GCD 與 LCM , 輾轉相除法

GCD ( Great Common Divisor ) - In mathematics, the greatest common divisor(gcd), also known as the greatest common factor(gcf), or highest common factor (hcf), of two or more integers (at least one of which is not zero), is the largest positive integer that divides the numbers without a remainder.
數學型式的說法,假設有 n 個正整數 a1 ,a2, a3 , ... , an  , 則存在 k 個 正整數 d1 , d2 , d3 , d4 , ... , dk-1 , dk , k < max { a1 ,a2, a3 , ... , an } , max means the largest number among a1 ,a2, a3 , ... , and an . 則 max { d1 , d2 , d3 , d4 , ... , dk-1 , dk } < max { a1 ,a2, a3 , ... , an } , if d = max { d1 , d2 , d3 , d4 , ... , dk-1 , dk } and d | ai ,   i  =  1,2,3,4, ..., n , then d is the great common divisor (G.C.D) of  a1 ,a2, a3 , ... , and an . 
For example , There exist  three numbers 12 , 24 and 36 . then find their GCD .   
A way of finding it is to find all divisors of each number. 
divisors of 12 are 1,2,3,4,6, and 12 
divisors of 24 are 1,2,3,4,6,8,12, and 24 
divisors of 36 are 1,2,3,4,6,8,12,18, and 36 
Analysis above results , we find 12's largest divisor is 12 and 24's largest divisor is 24 and 36 's largest divisor is 36. 36 can divided 36 , but can't divided 24 and 12. 24 is same. Just only 12 can divide three numbers . So , 12 is the G.C.D of them.
一般而言,G.C.D. 使用符號 gcd ( a1 ,a2, a3 , ... , an ) 表示求 a1 ,a2, a3 , ... , an  的最大公因數.
But according to above method , it is low effective way. 現在,使用輾轉相除法即可簡化步驟.
輾轉相除法 - Euclidean algorithm  
輾轉相除法 , Basically , this is a fast way to find the GCD between two numbers a ,b ; a , b ∈ N . if a > b , then we let a = kb + b0 , b0 , k ∈ N .  

If b0 ≠ 0 , we replace a by b and b by b0 and obtain a new equation. 
b = k1 × b0 + b1  and repeat this step till bi  = 0 , i = 0,1,2,3, ... , n ; n represents the times of executing Euclidean algorithm , if bi  = 0 , then bi+1  is the G.C.D. of a and b .  

For example , Given two numbers 36 and 48 , find their GCD .  
We use euclidean algorithm and factorize it as below :  

348 = 9 × 36 + 24 

36  =  1 × 24 + 12  

24  =  2 × 12 + 0  .... this is final step 
Therefore , 12 is their G.C.D. 

If we use divisor factorization for above two numbers , the effectiveness is poor. 

The fact that (a,b) = (b,r) , a , b , r ∈ N 
let (a,b) =d and (b,r) =e , then d | a and d | b and meanwhile , e | b and e | r . 
∵ a = kd , b = hd and a > b , then d | a - qb ,  q ∈ N .  

And what is LCM ?   
LCM - Explain it in wiki .