基础数论入门

2019-04-13 21:59发布

站内文章 / 模拟电子
10214 0 1310

（一）定理和性质

一、裴蜀定理

如果 a,b∈N" role="presentation">a,b∈N , (a,b)=d" role="presentation">(a,b)=d 那么一定存在 x,y" role="presentation">x,y 使得 d|(a∗x+b∗y)" role="presentation">d|(a∗x+b∗y)
证明：非常简单，鉴于可能有数论刚入门的OIer所以这里简单证明一下：
因为(a,b)=d" role="presentation">(a,b)=d
所以我们就可以假设 a=p∗d" role="presentation">a=p∗d , b=q∗d" role="presentation">b=q∗d
那么a∗x+b∗y=p∗d∗x+q∗d∗y=d∗(p∗x+q∗y)" role="presentation">a∗x+b∗y=p∗d∗x+q∗d∗y=d∗(p∗x+q∗y) 得证

二、整除的性质

a|c,b|c,(a,b)=1⇒ab|c" role="presentation">a|c,b|c,(a,b)=1⇒ab|c
a|bc,(a,b)=1⇒a|c" role="presentation">a|bc,(a,b)=1⇒a|c
p|ab⇒p|a或p|b" role="presentation">p|ab⇒p|a或p|b 正确性显然

三、同余

a≡b(mod m)⇐⇒m|(a−b)" role="presentation">a≡b(mod m)⇐⇒m|(a−b)
a≡b(mod m),a≡b(mod n)⇒a≡b(mod [m,n])" role="presentation">a≡b(mod m),a≡b(mod n)⇒a≡b(mod [m,n])
(k,m)=d,k∗a≡k∗a′(mod m)⇒a≡a′(mod md)" role="presentation">(k,m)=d,k∗a≡k∗a′(mod m)⇒a≡a′(mod md) 第二个式子证明：
(a−b)=x∗m=y∗n=k∗[m,n]" role="presentation">(a−b)=x∗m=y∗n=k∗[m,n] 第三个式子证明：
k=q∗d,m=p∗d" role="presentation">k=q∗d,m=p∗d
k∗a−k∗a′=c∗m" role="presentation">k∗a−k∗a′=c∗m
a−a′=c∗mk=c∗mq∗d=cq∗md" role="presentation">