简单数论总结(整除)
整除的几个性质
-
传递性:如果 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
显然成立,得证 -
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)
显然成立,得证 -
设 m m m不为 0 0 0,则 a ∣ b a|b a∣b等价于 m a ∣ m b ma|mb ma∣mb
证明:
额……这个就不证了吧 -
设整数 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,得证 -
若 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 :
- a = k 1 × n + m 1 a=k1×n+m1 a=k1×n+m1
- 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
模运算的放缩性
- 证明:
设 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
则原式显然成立 - 证明:
设 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可以发现,两式子相同……
运用:快速幂
例子可见本人博客。