一、常用定義定理
1.整除:設(shè)a,b∈Z,a≠0,如果存在q∈Z使得b=aq,那么稱b可被a整除,記作a|b,且稱b是a的倍數(shù),a是b的約數(shù)。b不能被a整除,記作a b.
2.帶余數(shù)除法:設(shè)a,b是兩個給定的整數(shù),a≠0,那么,一定存在唯一一對整數(shù)q與r,滿足b=aq+r,0≤r<|a|,當(dāng)r=0時a|b。
3.輾轉(zhuǎn)相除法:設(shè)u0,u1是給定的兩個整數(shù),u1≠0,u1 u0,由2可得下面k+1個等式:u0=q0u1+u2,02<|u1|;
u1=q1u2+u3,032;
u2=q2u3+u4,043;
…
uk-2=qk-2u1+uk-1+uk,0kk-1;
uk-1=qk-1uk+1,0k+1k;
uk=qkuk+1.
4.由3可得:(1)uk+1=(u0,u1);(2)d|u0且d|u1的充要條件是d|uk+1;(3)存在整數(shù)x
0,x1,使uk+1=x0u0+x1u1.
5.算術(shù)基本定理:若n>1且n為整數(shù),則