一、整除的概念
定義：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<b
證明：（證明q,r唯一）
假設 ? q1,r1∈Z使得a=q1*b+r1,0≤r1<b
∵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<b，0≤r1<b
∴0≤|r-r1|<b與|b| ≤|r-r1|相互矛盾，因此假設不成立，故r=r1
∴b*(q1-q)=r-r1=0
又∵b≠0
∴q1=q
定理五：r=<a>b(此處b為下標，表示a除以b所得的非負最小剩余)
①<a1±a2>=<<a1>±<a2>>（除數都為b，下標省略）
②<a1*a2>=<<a1>*<a2>>
證明：? q1,q2,q使得
a1=b*q1+<a1>
a2=b*q2+<a2>
a1*a2=b*q+<a1*a2>
∴<a1*a2>=a1*a2-b*q
=b*b*q1*q2+b*q1*<a2>+b*q2*<a1>+<a1>*<a2>-b*q
=b*(b*q1*q2+q1*<a2>+q2*<a1>-q)+<a1>*<a2>
令Q=(b*q1*q2+q1*<a2>+q2*<a1>-q),則<a1*a2>=b*Q+<a1>*<a2>
因此，<a1*a2>=<<a1>*<a2>>
二、最大公因數與輾轉相除
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<b)
①若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) ∴(b,r1)=(r1,r2)
r1=r2*q3+r3 (0＜r3<r2) ∴(r1,r2)=(r2,r3)
.
.
.
r(n-2)=r(n-1)*qn+rn (0＜rn<r(n-1)) ∴(r(n-2),r(n-1))=(r(n-1),rn)
r(n-1)=r(n)*q(n+1)+r(n+1) (0＜r(n+1)<rn) ∴(r(n-1),rn)=(rn,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)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/16229.html
標籤：其他