大学生网站建设,wordpress 空白页面,微信公众号平台怎么开发,张店学校网站建设哪家好基本概念
在数论中#xff0c;整除不得不说是一种最为基础的知识了。 a a a 整除 b b b#xff0c;记作 a ∣ b a|b a∣b 设 a , b ∈ Z a,b\in\Z a,b∈Z 且 b ≠ 0 b\ne 0 b0#xff0c;则 b ∣ a b|a b∣a 当且仅当 ∃ q ∈ Z \exist q\in\Z ∃q∈Z 满足 q b …基本概念
在数论中整除不得不说是一种最为基础的知识了。 a a a 整除 b b b记作 a ∣ b a|b a∣b 设 a , b ∈ Z a,b\in\Z a,b∈Z 且 b ≠ 0 b\ne 0 b0则 b ∣ a b|a b∣a 当且仅当 ∃ q ∈ Z \exist q\in\Z ∃q∈Z 满足 q b a qba qba
同余可以看做是整除的进阶版了。 a a a 除以 b b b 的余数记作 a m o d b a\mod b amodb 设 a , b ∈ Z a,b\in\Z a,b∈Z 且 b ≠ 0 b\ne 0 b0则唯一存在 q ∈ Z q\in\Z q∈Z 满足 q b r a qbra qbra 使得 0 ≤ r b 0\le rb 0≤rb称为带余除法记 a m o d b r a\mod br amodbr 设 x , y , m ∈ Z x,y,m\in\Z x,y,m∈Z 且 m ≠ 0 m\ne 0 m0当且仅当 x m o d m y m o d m x\mod my\mod m xmodmymodm称 x x x 与 y y y 在模 m m m 意义下同余记作 x ≡ y ( m o d m ) x\equiv y\pmod m x≡y(modm)
基本性质
作为一个 OIer似乎并不需要知道以下性质的证明虽然很好证就是了。
若 a ∣ b , b ∣ c a|b,b|c a∣b,b∣c则 a ∣ c a|c a∣c 不妨设 b p a , c q b bpa,cqb bpa,cqb 其中 p , q ∈ Z p,q\in\Z p,q∈Z 联立得 c p q a p q ⋅ a cpqapq\cdot a cpqapq⋅a 则 a ∣ c a|c a∣c若 a ∣ b a∣b a∣b 且 a ∣ c a∣c a∣c则 a ∣ b x c y ∀ x , y ∈ Z a|bxcy\forall x,y\in\Z a∣bxcy∀x,y∈Z 不妨设 b p a , c q a bpa,cqa bpa,cqa 其中 p , q ∈ Z p,q\in\Z p,q∈Z 则 b x c y p x a q y a ( p x q y ) ⋅ a bxcypxaqya(pxqy)\cdot a bxcypxaqya(pxqy)⋅a 则 a ∣ b x c y a|bxcy a∣bxcy若 a ∣ b a∣b a∣b 且 c ∣ d c∣d c∣d则 a c ∣ b d ac∣bd ac∣bd 不妨设 b p a , d q c bpa,dqc bpa,dqc 其中 p , q ∈ Z p,q\in\Z p,q∈Z 则 b d p a ⋅ q c p q ⋅ a c bdpa\cdot qcpq\cdot ac bdpa⋅qcpq⋅ac 则 a c ∣ b d ac|bd ac∣bd p ∣ ( a − b ) p∣(a−b) p∣(a−b) 等价于 a ≡ b ( m o d p ) a\equiv b\pmod p a≡b(modp) 不妨设 b , d q c b,dqc b,dqc 其中 p , q ∈ Z p,q\in\Z p,q∈Z 则 b d p a ⋅ q c p q ⋅ a c bdpa\cdot qcpq\cdot ac bdpa⋅qcpq⋅ac 则 a c ∣ b d ac|bd ac∣bd a ≡ a ( m o d p ) a\equiv a \pmod p a≡a(modp) 易证。 a ≡ b ( m o d p ) a\equiv b \pmod p a≡b(modp) 等价于 b ≡ a ( m o d p ) b\equiv a \pmod p b≡a(modp) 易证。若 a ≡ b ( m o d p ) a\equiv b \pmod p a≡b(modp) 且 b ≡ c ( m o d p ) b\equiv c \pmod p b≡c(modp)则 a ≡ c ( m o d p ) a\equiv c \pmod p a≡c(modp) 不妨设 b a k 1 p , c b k 2 p bak_1p,cbk_2p bak1p,cbk2p 则 c a k 1 p k 2 p a ( k 1 k 2 ) ⋅ p cak_1pk_2pa(k_1k_2)\cdot p cak1pk2pa(k1k2)⋅p 则 a ≡ c ( m o d p ) a\equiv c \pmod p a≡c(modp)若 a ≡ b ( m o d p ) a\equiv b \pmod p a≡b(modp)则 a c ≡ b c ( m o d p ) a c\equiv b c \pmod p ac≡bc(modp) 不妨设 b a k 1 p bak_1p bak1p 则 b c a k 1 p c ≡ a c ( m o d p ) bcak_1pc\equiv ac\pmod p bcak1pc≡ac(modp) 则 a c ≡ b c ( m o d p ) a c\equiv b c \pmod p ac≡bc(modp)若 a ≡ b ( m o d p ) a\equiv b \pmod p a≡b(modp)则 a c ≡ b c ( m o d p ) ac\equiv bc \pmod p ac≡bc(modp) 不妨设 b a k 1 p bak_1p bak1p 则 b c ( a k 1 p ) ⋅ c a c k 1 p c ≡ a c ( m o d p ) bc(ak_1p)\cdot cack_1pc\equiv ac\pmod p bc(ak1p)⋅cack1pc≡ac(modp) 则 a c ≡ b c ( m o d p ) ac\equiv bc \pmod p ac≡bc(modp)若 a ≡ b ( m o d p ) a\equiv b \pmod p a≡b(modp)则 a n ≡ b n ( m o d p ) a^n\equiv b^n \pmod p an≡bn(modp) 不妨设 b a k 1 p bak_1p bak1p 则由二项式定理 b n ( a k 1 p ) ⋅ c ∑ i 0 n ( k i ) ⋅ a i ( k 1 p ) n − i ≡ a n ( m o d p ) b^n(ak_1p)\cdot c\sum_{i0}^n{k\choose i}\cdot a^i(k_1p)^{n-i}\equiv a^n\pmod p bn(ak1p)⋅c∑i0n(ik)⋅ai(k1p)n−i≡an(modp) 则 a n ≡ b n ( m o d p ) a^n\equiv b^n\pmod p an≡bn(modp)
