最大公约数

在解有关最大公约数、最小公倍数的问题时，常用到以下结论　
- 如果两个自然数是互质数，那么它们的最大公约数是1，最小公倍数是这两个数的乘积。
  　　例如8和9，它们是互质数，所以（8，9）=1，[8，9]=72。
- 2）如果两个自然数中，较大数是较小数的倍数，那么较小数就是这两个数的最大公约数，较大数就是这两个数的最小公倍数。
  　　例如18与3，18÷3=6，所以（18，3）=3，[18，3]=18。
- （3）两个整数分别除以它们的最大公约数，所得的商是互质数。
  　　例如8和14分别除以它们的最大公约数2，所得的商分别为4和7，那么4和7是互质数。
- （4）两个自然数的最大公约数与它们的最小公倍数的乘积等于这两个数的乘积。
  　　例如12和16，（12，16）=4，[12，16]=48，有4×48=12×16，即（12，16）× [12，16]=12×16。
- （5）GCD(a,b) is the smallest positive linear combination of a and b. a与b的最大公约数是最小的a与b的正线性组合,即对于方程xa+yb=c来说,若x,a,y,b都为整数,那么c的最小正根为gcd(a,b).