文档介绍：第十二讲数论
第一节最大公约数
首先,我们来回顾一下公约数和最大公约数的概念:如果d是a的约数并且也是b的约数,则d是a与b的公约数。例如,30的约数为1,2,3,5,6,10,15,30; 24的约数为1,2,3,4,6,12,24; 因此24与30的公约数1,2,3,6。1是任意两个整数的公约数。
两个不同时为0的整数a与b的最大公约是其值为最大的公约数,表示为gcd(a,b)。显然,gcd(24,30)=6。在这节中,我们仅限于对非负整数的情况进行讨论。这一限制是有道理的,因为gcd(a,b)=gcd(│a│,│b│)。
不妨设a>=b,一种十分容易想到的算法是:枚举1到b的所有整数,在能同时整除a和b的数中取最大的。这个算法的时间复杂度为O(min(a,b)),当min(a,b)较大的时候程序要执行比较长的时间。
    在引出新算法之前,我们先来证明一个被称为gcd(欧几里德)的递归定理: gcd(a,b)=gcd(b,a  mod  b)
证明:
我们只要证明出gcd(a,b)与gcd(b,a  mod  b)可互相整除,上式一定成立。设d=gcd(a,b)。将a mod b 化成a与b的线性组合
    a mod b=a-a div b * b
    由于d能整除a和b,因此d一定能整除a与b的线性组合,即d能整除(a mod b)。又因为d能整除b和(a mod b),显然d(=gcd(a,b))能整除gcd(b,a mod b)。
    同理可证:gcd(b,a mod b)能整除gcd(a,b)
下述算法是一个直接基于gcd定理之上的递归程序。该函数输入非负整数a、 b,返回a和b的最大公约数。   
 function gcd(a,b:longint):longint;
  begin
   if b=0 then
    gcd:=a
   else
    gcd:=gcd(b,a mod b)
  end;
由于递归边界gcd(a,0)=a正确且递归调用过程中第二个值参严格递减, 所以算法不可能无限递归下去,在运行终止时总能求出正确的答案。例如gcd(30,21)的计算过程
    gcd(30,21)=gcd(21,9)=gcd(9,3)=gcd(3,0)=3
    在这个计算过程中三次递归调用了gcd。此算法的时间复杂度为O(log(Max(a,b)))。
同理求这两个数的最小公倍数LCM ( a , b ),直接利用公式:
LCM ( a , b ) * GCD( a , b ) = a * b即可。 
    生活中许多有趣的问题,可以运用gcd定理来解答。
例12_1 狼找兔子
一座山周围有n个洞,逆时针编号为0,1,2,...n-1。
而一只狼从0号洞开始,逆时针方向计数,每遇到m个洞就进洞找兔子。例如n=5,m=3,狼经过的洞依次为0,3,1,4,2,0。
    输入n、m。试问兔子有没有幸免的机会?如果有,该藏在哪儿?
分析:
不妨让兔子躲在一号洞。因为若狼能从0号洞到达1号洞,则它必能从1号洞到达2,...,n-1号洞,兔子难逃厄运。反过来说,若有安全洞,则1号洞就是其中的一个。