整除的幾個性質

1. 傳遞性：如果 a ∣ b a|b a∣b且 b ∣ c b|c b∣c，則 a ∣ c a|c a∣c
   證明：
   ∵ a ∣ b ∵a|b ∵a∣b ∴ ∴ ∴令 a × x = b ( x ∈ Z a×x=b(x∈Z a×x=b(x∈Z且 x ≠ 0 ) x≠0) x?=0)
   ∵ b ∣ c ∵b|c ∵b∣c ∴ ∴ ∴令 b × y = c ( y ∈ Z b×y=c(y∈Z b×y=c(y∈Z且 y ≠ 0 ) y≠0) y?=0)
   ∴ ∴ ∴即證： a ∣ a × x × y a|a×x×y a∣a×x×y
   顯然成立，得證

2. a ∣ b a|b a∣b且 a ∣ c a|c a∣c可化為對于任意的整數 x x x， y y y，有 a ∣ ( b x + c y ) a|(bx+cy) a∣(bx+cy)
   證明：
   a s = b as=b as=b ( s ≠ 0 , s ∈ Z ) (s≠0,s∈Z) (s?=0,s∈Z)
   a t = c at=c at=c ( t ≠ 0 , t ∈ Z ) (t≠0,t∈Z) (t?=0,t∈Z)
   ∴ b x + c y = a s x + a t y = a ( s x + t y ) ∴bx+cy=asx+aty=a(sx+ty) ∴bx+cy=asx+aty=a(sx+ty)
   ∴ ∴ ∴即證： a ∣ a ( s x + t y ) a|a(sx+ty) a∣a(sx+ty)
   顯然成立，得證

3. 設 m m m不為 0 0 0，則 a ∣ b a|b a∣b等價于 m a ∣ m b ma|mb ma∣mb
   證明：
   額……這個就不證了吧

4. 設整數 x , y x,y x,y滿足下式： a x + b y = 1 ax+by=1 ax+by=1，且 a ∣ n a|n a∣n， b ∣ n b|n b∣n，那么 ( a b ) ∣ n (ab)|n (ab)∣n
   證明 ( a b ) ∣ n (ab)|n (ab)∣n
   a s = n as=n as=n ( s ≠ 0 , s ∈ Z ) (s≠0,s∈Z) (s?=0,s∈Z)
   b t = n bt=n bt=n ( t ≠ 0 , t ∈ Z ) (t≠0,t∈Z) (t?=0,t∈Z)
   欲證： ( a b ) ∣ n (ab)|n (ab)∣n
   即證： n a b ∈ Z \frac{n}{ab}∈Z abn?∈Z
   又 ∵ n a b = n × 1 a b = n × a x + b y a b = n × ( x b + y a ) = n × x b + n × y a = t x + s y ∵\frac{n}{ab}=n×\frac{1}{ab}=n×\frac{ax+by}{ab}=n×(\frac{x}{b}+\frac{y}{a})=\frac{n×x}{b}+\frac{n×y}{a}=tx+sy ∵abn?=n×ab1?=n×abax+by?=n×(bx?+ay?)=bn×x?+an×y?=tx+sy
   ∴ ∴ ∴ n a b ∈ Z \frac{n}{ab}∈Z abn?∈Z，得證

5. 若 b = q ? d + c b=q*d+c b=q?d+c，那么 d ∣ b d|b d∣b的充要條件是 d ∣ c d|c d∣c
   自己證吧，我不想打了……（提示： b = q d + x d = ( q + x ) d , ( x ≠ 0 , x ∈ Z ) b=qd+xd=(q+x)d,(x≠0,x∈Z) b=qd+xd=(q+x)d,(x?=0,x∈Z) ）

數論小常識

較簡單，就不解釋了，

模運算的分配率

對于整數 a a a， b b b，其中 b b b不為 0 0 0，求 a a a除以 b b b的余數，稱為 a a a模 b b b，記為 a % b a\%b a%b.
模運算的性質：

分配率：模運算對加、減、乘具有分配率

假設對整數 a , b , m 1 , m 2 , n a, b, m1, m2,n a,b,m1,m2,n ：

1. a = k 1 × n + m 1 a=k1×n+m1 a=k1×n+m1
2. b = k 2 ? n + m 2 b=k2*n+m2 b=k2?n+m2

因此 ( a × b ) % n = ( a % n ) ? ( b % n ) = m 1 × m 2 (a×b)\%n=(a\%n)*(b\%n)=m1×m2 (a×b)%n=(a%n)?(b%n)=m1×m2

模運算的放縮性

1. 證明：
   設 a = b × s + c a=b×s+c a=b×s+c
   ∴ a × d = ( b × s + c ) × d ∴a×d=(b×s+c)×d ∴a×d=(b×s+c)×d
   ∴ b × d × s + c × d = a × d ∴b×d×s+c×d=a×d ∴b×d×s+c×d=a×d
   則原式顯然成立
2. 證明：
   設 a = b × s + c a=b×s+c a=b×s+c
   b d × s + c d = a d \frac{b}{d}×s+\frac{c}{d}=\frac{a}{d} db?×s+dc?=da?
   ∴ ( b d , a b , s ∈ Z ) ∴(\frac{b}{d},\frac{a}{b},s∈Z) ∴(db?,ba?,s∈Z)
   ∴ a c ∈ Z ∴\frac{a}{c}∈Z ∴ca?∈Z

附加第三個式子：

a b % c = a % ( b × c ) b \frac{a}{b}\%c=\frac{a\%(b×c)}{b} ba?%c=ba%(b×c)?

證明：
由縮放性1的性質可得：在兩邊同時乘上 b b b可以發現，兩式子相同……

運用：快速冪
例子可見本人博客，