数论-整除+欧几里得+扩展欧几里得
一、整除的概念
定义：a,b是两个任意整数，b≠0，若存在整数q，使得a=b*q,则称 a能够被b整除，也称b能整除a,也称b是a的因数，也称a为b的倍数。用记号b|a表示。
整除的性质：
①任意一个整数都可以整除0，即?b,b|0(因为0*b=0)
②1可以整除任意一个整数,?a,1|a
③如果b|a,那么b| |a|(a的绝对值)
④若c|b,b|a,则c|a
⑤若b|a,则c*b|c*a
⑥若b|a,且a≠0，则|b| ≤ |a|
⑦若c|a,c|b，则c|(a+b)*m
⑧若c*b|c*a，则 b|a
⑨若b|a且a≠0，则(a/b) | a
定理一：a与|a|的所有约束是相同的，a的约数是成对出现的
b | a <-> (-b) | a
a=b*q
a=(-b)*(-q)
定理二：a,b是整数，且都是m的倍数，则a±b都是m的倍数
证明：
a=m*a1
b=m*b1
故a±b=m*(a1+b1),因此，a±b即为m的倍数
定理三：若a1,a2,...an都是m的倍数，则q1*a1+q2*a2+...+qn*an是m的倍数（其中qi为整数）
证明：
∵ai为m的倍数
故q1*a1+q2*a2+...+qn*an
=q1*b1*m+q2*b2*m+...qn*bn*m
=m*(q1*b1+q2*b2+...qn*bn)
因此，q1*a1+q2*a2+...+qn*an是m的倍数
定理四：带余除法
? a,b ∈Z,b>0,? q,r∈Z,使得a=b*q+r,0≤r 证明：（证明q,r唯一） 假设 ? q1,r1∈Z使得a=q1*b+r1,0≤r1 ∵a=b*q+r 故0=b*(q-q1)+(r-r1) ∴b(q1-q)=(r-r1)即b|(r-r1) ∴|b| ≤|r-r1| 假设(r-r1)≠0 ∵ 0≤r ∴0≤|r-r1| ∴b*(q1-q)=r-r1=0 又∵b≠0 ∴q1=q 定理五：r=b(此处b为下标，表示a除以b所得的非负最小剩余) ① ② 证明：? q1,q2,q使得 a1=b*q1+ a2=b*q2+ a1*a2=b*q+ ∴ =b*b*q1*q2+b*q1* =b*(b*q1*q2+q1* 令Q=(b*q1*q2+q1* 因此， 二、最大公因数与辗转相除 d为a1,a2...an的最大公因数-> d|a1 , d|a2, ...d|an，记作(a1,a2...an) 用数学符号表示: ①? i,1≤i≤n,(a1,a2,..an)|ai ②? m,m|ai, 则m≤(a1,a2,...an) 定理一：若a=b*q+c(a,b,c不全为0)，则(a,b)=(b,c) 证明： ∵(a,b)|a, (a,b)|b , c=a-b*q ∴(a,b) | c ∴(a,b)为b和c的因数，即(a,b)≤(b,c) 同理，(b,c)|b,(b,c)|c ,a=b*q+c ∴ (b,c)|a ∴(b,c)为b和a的因数，即(b,c)≤(a,b) ∵(a,b)≤(b,c)且(b,c)≤(a,b) 故(a,b)=(b,c) 定理二、?a>0,b>0,则(a,b)(辗转相除-欧几里得) 解： a=b*q1+r1(0≤r1 ①若r1＝0，则(a,b)=b ∵a=b*q1 ∴b|a ,b|b ∴b|(a,b)即b≤(a,b) 又∵(a,b)≤b ∴(a,b)=b ②若r1≠0，(a,b)=(b,r1)（迭代） b=r1*q2+r2 (0＜r2 r1=r2*q3+r3 (0＜r3 r(n-2)=r(n-1)*qn+rn (0＜rn r(n-1)=r(n)*q(n+1)+r(n+1) (0＜r(n+1) 最后定有一个n存在，使得r(n+1)=0,故(r(n-1),rn)=rn 即rn=(r(n-1),rn)=(a,b) 定理三：?a>0,b>0,?m,n使得(a,b)=ma+mb（扩展的欧几里得） 证明：（回代） r(n-1)=rn*q(n+1) (r(n+1)=0) r(n-2)=r(n-1)*qn+rn -> rn=r(n-2)-r(n-1)*qn r(n-3)=r(n-2)*q(n-1)+r(n-1) -> r(n-1) =r(n-3) - r(n-2)*q(n-1) ... rn=r(n-2)-(r(n-3) - r(n-2)*q(n-1))*qn =(1+q(n-1)*qn)*r(n-2)-r(n-3)*qn =... =r1*Q+b*Q1=(a-b*q1)+b*Q1=ma+nb 例：a=288 ,b=158 （迭代） 288=1 *158 + 130 158=1*130 +28 130=4*28 +18 28 =1*18+10 18=1*10+8 10=1*8+2 8=4*2+0 因此最大公约数为2 （回代） 2=10-1*8 =10-1*(18-1*10)=10*2-18*1 =(28-1*18)*2-18*1=2*28-18*3 =2*28-(130-4*28)*3=14*28 - 3*130 =14*(158-1*130) -3*130=14*158-17*130 =14*158-17*(288-1*158) =31*158-17*288 即 nb+ma=(a,b) 扩展：?a,b>0,?唯一的q,r,|r|≤b/2,使得a=b*q+r(利用带余除法证明) 证明：根据带余除法可知， ?q1,r1使得a=b*q1+r1(0≤r1 若r1≤b/2,令r=r1,q=q1则显然满足,a=b*q+r 若r1＞b/2，令r=r1-b(|r|＜b/2)，q1=q1+1，则 a=b*q1+r1=b*(q1+1)+r1-b ∵b/2 ∴-b/2 ∴|r1-b|
故，综上所述，,?唯一的q,r,|r|≤b/2,使得a=b*q+r 举例： a=288 b=158 288=1*158+130=2*158-28 158=28*6-10 28=10*3-2 10=2*5 算出最大公约数为2（这种方法相对于上一种方法所需步骤更少，能很快得出答案） 定理：a|b*c,且(a,b)=1,则a|c 证明：?m,n,使得(a,b)=m*a+n*b ∵(a,b)=1 ∴m*a+n*b=1 m*a*c+n*b*c=c ∵a|b*c ，故?q, b*c=a*q ∴m*a*c+n*a*q=c 即a(m*c+n*q)=c 所以a|c