@(verilog)

求最大公因数的常用算法为辗转相除法，又被称为欧几里德（Euclidean）算法， 是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》（第VII卷，命题i和ii）中，而在中国则可以追溯至东汉出现的《九章算术》。

两个数的最大公约数是指能同时整除它们的最大正整数。辗转相除法的基本原理是：两个数的最大公约数等于它们中较小的数和两数之差的最大公约数。 例如，252和105的最大公约数是21（252 = 21 × 12；105 = 21 × 5）；因为252 − 105 = 147，所以147和105的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时，所剩下的还没有变成零的数就是两数的最大公约数。

可以简单证明一下： 设 A A A和 B B B的最大公因数为 g c d = X gcd=X gcd=X,且 A > B A>B A>B,可以将他们表示为： A = m X , m ∈ Z B = n X , n ∈ Z A = mX, m\in Z \\ B = nX, n\in Z A=mX,m∈ZB=nX,n∈Z 其中， m , n m,n m,n互质。计 A , B A,B A,B的差为 C C C： C = ( m − n ) X C = (m-n)X C=(m−n)X 首先，可以证明， m − n m-n m−n与 m , n m,n m,n都互质，因为 m − n m-n m−n如果跟 n n n有公因数，则 m , n m,n m,n必也有公因式，违反了条件。因此互质数的和差与原来两数都互质。 其次，由于 m − n m-n m−n与 n n n互质，因此 B , C B,C B,C的最大公因式就是 X X X,因为没办法再从 m − n m-n m−n与 n n n中提出一个因式放到 X X X里。 所以， A , B A,B A,B的最大公约数就是 B , C B,C B,C的最大公约数。 由此，就可以将 A , B A,B A,B“辗转”地相互做差，这样不断地进行，最后一定会出现要做差的两个数都为 X X X的情形，因为做差做到最后， ( m ′ − n ′ ) (m'-n') (m′−n′)与 n ′ n' n′一定会变成最小的互质数对 ( 1 , 1 ) (1,1) (1,1),也就是经过若干次辗转后较小的那个数与他们的差相等，此时就得到了最大公约数。

事实上，上面的是辗转相减法，为了加速相减的过程，实际上可以使用除法加速辗转的过程。（除法就是若干次减法）

最小公倍数实际上等于两数之积除以他们的最大公约数。为什么呢？还是可以从上面的假设进行推导： 首先我们知道，互质数的最小公倍数一定是他们的积。而要求 A , B A,B A,B的最小公倍数，因为它们已经有了最大的公约数 X X X,所以其实只要求互质的两个数 m , n m,n m,n的最小公倍数，所以 A , B A,B A,B的最小公倍数 l c m = m n X = A B / X lcm=mnX=AB/X lcm=mnX=AB/X。