2. 科技
    3. 初等数论 课堂笔记 第三章 -- 剩余类，剩余类环，完全剩余系

    初等数论 课堂笔记 第三章 -- 剩余类，剩余类环，完全剩余系

    科技2025-12-17  10

    索引

    剩余类, 剩余类环定理: Z = K 0 ⋃ K 1 ⋃ ⋯ ⋃ K m − 1 ,   K i ⋂ K j = ∅ ( ∀ i ≠ j ) \mathbb{Z}={{K}_{0}}\bigcup {{K}_{1}}\bigcup \cdots \bigcup {{K}_{m-1}},\text{ }{{K}_{i}}\bigcap {{K}_{j}}=\varnothing \left( \forall i\ne j \right) Z=K0​⋃K1​⋃⋯⋃Km−1​, Ki​⋂Kj​=∅(∀i​=j)定理: 两个整数来自模 m m m同一个剩余类 ⇔ \Leftrightarrow ⇔两个数的差被 m m m整除。定理: 若 p p p是素数，则 Z / p Z \mathbb{Z}/p\mathbb{Z} Z/pZ是一个域，记为 F p {{\mathbb{F}}_{p}} Fp​。定理: 若 m m m是合数， Z / m Z \mathbb{Z}/m\mathbb{Z} Z/mZ一定不是域。 完全剩余系定理: m m m个整数作成模 m m m的一个完全剩余系 ⇔ \Leftrightarrow ⇔两两对模 m m m不同余。定理: 设 a 0 , a 1 , ⋯   , a m − 1 {{a}_{0}},{{a}_{1}},\cdots ,{{a}_{m-1}} a0​,a1​,⋯,am−1​是模 m m m的完全剩余系， gcd ⁡ ( a , m ) = 1 \gcd \left( a,m \right)=1 gcd(a,m)=1，则 a a 0 + b ,   a a 1 + b ,   ⋯   , a a m − 1 + b a{{a}_{0}}+b,\text{ }a{{a}_{1}}+b,\text{ }\cdots ,a{{a}_{m-1}}+b aa0​+b, aa1​+b, ⋯,aam−1​+b也是模 m m m的完全剩余系。定理: 设 m 1 , m 2 ∈ Z ,  gcd ( m 1 , m 2 ) = 1 {{m}_{1}},{{m}_{2}}\in \mathbb{Z},\text{ gcd}\left( {{m}_{1}},{{m}_{2}} \right)=1 m1​,m2​∈Z, gcd(m1​,m2​)=1，设 x 1 {{x}_{1}} x1​通过模 m 1 {{m}_{1}} m1​的完全剩余系 K 1 K_1 K1​， x 2 {{x}_{2}} x2​通过模 m 2 {{m}_{2}} m2​的完全剩余系 K 2 K_2 K2​，则 m 1 x 2 + m 2 x 1 {{m}_{1}}{{x}_{2}}+{{m}_{2}}{{x}_{1}} m1​x2​+m2​x1​通过模 m 1 m 2 {{m}_{1}}{{m}_{2}} m1​m2​的完全剩余系 K K K。推广: 若 m 1 , m 2 , ⋯   , m k {{m}_{1}},{{m}_{2}},\cdots ,{{m}_{k}} m1​,m2​,⋯,mk​是 k k k个两两互素的正整数， x 1 , x 2 ⋯   , x k {{x}_{1}},{{x}_{2}}\cdots ,{{x}_{k}} x1​,x2​⋯,xk​分别通过模 m 1 , m 2 , ⋯   , m k {{m}_{1}},{{m}_{2}},\cdots ,{{m}_{k}} m1​,m2​,⋯,mk​的完全剩余系，则 M 1 x 1 + M 2 x 2 + ⋯ + M k x k {{M}_{1}}{{x}_{1}}+{{M}_{2}}{{x}_{2}}+\cdots +{{M}_{k}}{{x}_{k}} M1​x1​+M2​x2​+⋯+Mk​xk​通过模 m 1 m 2 ⋯ m k = m {{m}_{1}}{{m}_{2}}\cdots {{m}_{k}}=m m1​m2​⋯mk​=m的完全剩余系，其中 m = m i M i ,   i = 1 , 2 , ⋯   , k m={{m}_{i}}{{M}_{i}},\text{ }i=1,2,\cdots ,k m=mi​Mi​, i=1,2,⋯,k。

    剩余类, 剩余类环

    定义

    设 m ∈ Z > 0 m\in {{\mathbb{Z}}_{>0}} m∈Z>0​ ， r ∈ Z r\in \mathbb{Z} r∈Z， 0 ≤ r ≤ m − 1 0\le r\le m-1 0≤r≤m−1，则 K r = { n ∈ Z : n ≡ r (   m o d   m ) } {{K}_{r}}=\left\{ n\in \mathbb{Z}:n\equiv r\left( \bmod m \right) \right\} Kr​={n∈Z:n≡r(modm)} 叫做模 m m m的剩余类。 { K 0 , K 1 , ⋯   , K m − 1 } \left\{ {{K}_{0}},{{K}_{1}},\cdots ,{{K}_{m-1}} \right\} {K0​,K1​,⋯,Km−1​}构成模 m m m的剩余类环（环：加减乘封闭），写为 Z / m Z = { 0 , 1 , ⋯   , m − 1 } \mathbb{Z}/m\mathbb{Z}=\left\{ 0,1,\cdots ,m-1 \right\} Z/mZ={0,1,⋯,m−1}。环上的加法和乘法如下定义: K a + K b = K c   若   a + b ≡ c (   m o d   m ) {{K}_{a}}+{{K}_{b}}={{K}_{c}}\text{ }若\text{ }a+b\equiv c\left( \bmod m \right) Ka​+Kb​=Kc​ 若 a+b≡c(modm) K a ⋅ K b = K c   若   a b ≡ c (   m o d   m ) {{K}_{a}}\centerdot {{K}_{b}}={{K}_{c}}\text{ }若\text{ }ab\equiv c\left( \bmod m \right) Ka​⋅Kb​=Kc​ 若 ab≡c(modm)

    例子

    { 0 ‾ , 1 ‾ , 2 ‾ , 3 ‾ } \left\{ \overline{0},\overline{1},\overline{2},\overline{3} \right\} {0,1,2,3}是模4的剩余类环，在 Z / 4 Z \mathbb{Z}/4\mathbb{Z} Z/4Z中， 2 ‾ × 2 ‾ = 0 ‾ \overline{2}\times \overline{2}=\overline{0} 2×2=0。

    若 p p p是素数，则模 p p p的剩余类环成为一个有限域（加减乘除封闭），写作 F p = Z / p Z {{\mathbb{F}}_{p}}=\mathbb{Z}/p\mathbb{Z} Fp​=Z/pZ。 例如，在 F 7 = { 0 ‾ , 1 ‾ , 2 ‾ , 3 ‾ , 4 ‾ , 5 ‾ , 6 ‾ } {{\mathbb{F}}_{7}}=\left\{ \overline{0},\overline{1},\overline{2},\overline{3},\overline{4},\overline{5},\overline{6} \right\} F7​={0,1,2,3,4,5,6}中，由于 2 × 4 = 8 ≡ 1 (   m o d   7 ) 3 × 5 = 15 ≡ 1 (   m o d   7 ) 6 × 6 = 36 ≡ 1 (   m o d   7 ) \begin{aligned} & 2\times 4=8\equiv 1\left( \bmod 7 \right) \\ & 3\times 5=15\equiv 1\left( \bmod 7 \right) \\ & 6\times 6=36\equiv 1\left( \bmod 7 \right) \\ \end{aligned} ​2×4=8≡1(mod7)3×5=15≡1(mod7)6×6=36≡1(mod7)​ 因此有 2 ‾ × 4 ‾ = 1 ‾   ⇒   1 ‾ 2 ‾ = 4 ‾ 3 ‾ × 5 ‾ = 1 ‾   ⇒   1 ‾ 3 ‾ = 5 ‾ 6 ‾ × 6 ‾ = 1 ‾   ⇒   1 ‾ 6 ‾ = 6 ‾ \begin{aligned} & \overline{2}\times \overline{4}=\overline{1}\text{ }\Rightarrow \text{ }\frac{\overline{1}}{\overline{2}}=\overline{4} \\ & \overline{3}\times \overline{5}=\overline{1}\text{ }\Rightarrow \text{ }\frac{\overline{1}}{\overline{3}}=\overline{5} \\ & \overline{6}\times \overline{6}=\overline{1}\text{ }\Rightarrow \text{ }\frac{\overline{1}}{\overline{6}}=\overline{6} \\ \end{aligned} ​2×4=1 ⇒ 21​=43×5=1 ⇒ 31​=56×6=1 ⇒ 61​=6​

    在 F 13 = { 0 ‾ ,   1 ‾ ,   ⋯   ,   12 ‾ } {{\mathbb{F}}_{13}}=\left\{ \overline{0},\text{ }\overline{1},\text{ }\cdots ,\text{ }\overline{12} \right\} F13​={0, 1, ⋯, 12}中，不用穷举法求出 1 ‾ 5 ‾ \frac{\overline{1}}{\overline{5}} 51​。 解   令 1 ‾ 5 ‾ = a ‾ \frac{\overline{1}}{\overline{5}}=\overline{a} 51​=a，则有   5 ‾ ⋅ a ‾ = 1 ‾ ⇔ ( 13 k 1 + 5 ) ( 13 k 2 + a ) = 13 k + 1 ⇔ 5 a + 13 ( 13 k 1 k 2 + a k 1 + 5 k 2 − k ) = 1 ,   ∀ k , k 1 , k 2 ∈ Z \begin{aligned} & \text{ }\overline{5}\centerdot \overline{a}=\overline{1} \\ & \Leftrightarrow \left( 13{{k}_{1}}+5 \right)\left( 13{{k}_{2}}+a \right)=13k+1 \\ & \Leftrightarrow 5a+13\left( 13{{k}_{1}}{{k}_{2}}+a{{k}_{1}}+5{{k}_{2}}-k \right)=1,\text{ }\forall k,{{k}_{1}},{{k}_{2}}\in \mathbb{Z} \\ \end{aligned} ​ 5⋅a=1⇔(13k1​+5)(13k2​+a)=13k+1⇔5a+13(13k1​k2​+ak1​+5k2​−k)=1, ∀k,k1​,k2​∈Z​ 因此求解 a ‾ \overline{a} a等价于求解 5 a + 13 b = 1 ,   a , b ∈ Z 5a+13b=1,\text{ }a,b \in \mathbb{Z} 5a+13b=1, a,b∈Z （因为一方面 ( a , 13 k 1 k 2 + a k 1 + 5 k 2 − k ) \left( a,13{{k}_{1}}{{k}_{2}}+a{{k}_{1}}+5{{k}_{2}}-k \right) (a,13k1​k2​+ak1​+5k2​−k)本身就是 5 a + 13 b = 1 5a+13b=1 5a+13b=1的解；另一方面，由于 13 k 1 k 2 + a k 1 + 5 k 2 − k 13{{k}_{1}}{{k}_{2}}+a{{k}_{1}}+5{{k}_{2}}-k 13k1​k2​+ak1​+5k2​−k中 k k k的系数是 − 1 -1 −1，所以对于一个确定的 b b b，总能找到一组系数对 ( k , k 1 , k 2 ) \left( k,{{k}_{1}},{{k}_{2}} \right) (k,k1​,k2​)使得 b = 13 k 1 k 2 + a k 1 + 5 k 2 − k b=13{{k}_{1}}{{k}_{2}}+a{{k}_{1}}+5{{k}_{2}}-k b=13k1​k2​+ak1​+5k2​−k） 进行辗转相除法如下。 13 = 5 × 2 + 3 5 = 3 × 1 + 2 3 = 2 × 1 + 1 \begin{aligned} & 13=5\times 2+3 \\ & 5=3\times 1+2 \\ & 3=2\times 1+1 \\ \end{aligned} ​13=5×2+35=3×1+23=2×1+1​ 因此有 P 0 = 1 ,   P 1 = 2 ,   P 2 = 1 × 2 + 1 = 3 ,   P 3 = 1 × 3 + 2 = 5 Q 0 = 0 ,   Q 1 = 1 ,   Q 2 = 1 × 1 + 0 = 1 ,   Q 3 = 1 × 1 + 1 = 2 \begin{aligned} & {{P}_{0}}=1,\text{ }{{P}_{1}}=2,\text{ }{{P}_{2}}=1\times 2+1=3,\text{ }{{P}_{3}}=1\times 3+2=5 \\ & {{Q}_{0}}=0,\text{ }{{Q}_{1}}=1,\text{ }{{Q}_{2}}=1\times 1+0=1,\text{ }{{Q}_{3}}=1\times 1+1=2 \\ \end{aligned} ​P0​=1, P1​=2, P2​=1×2+1=3, P3​=1×3+2=5Q0​=0, Q1​=1, Q2​=1×1+0=1, Q3​=1×1+1=2​ 因此有特解 ( ( − 1 ) 3 P 3 , ( − 1 ) 2 P 2 ) = ( − 5 , 2 ) \left( {{\left( -1 \right)}^{3}}{{P}_{3}},{{\left( -1 \right)}^{2}}{{P}_{2}} \right)=\left( -5,2 \right) ((−1)3P3​,(−1)2P2​)=(−5,2)，方程的通解为 { a = − 5 − 13 t b = 2 + 5 t ,   t ∈ Z \left\{ \begin{aligned} & a=-5-13t \\ & b=2+5t \\ \end{aligned} \right.,\text{ }t\in \mathbb{Z} {​a=−5−13tb=2+5t​, t∈Z 在 Z \mathbb{Z} Z中， a ≡ − 5 ≡ 8 (   m o d   13 ) a\equiv -5\equiv 8\left( \bmod 13 \right) a≡−5≡8(mod13)，因此在 F 13 = Z / 13 Z {{\mathbb{F}}_{13}}=\mathbb{Z}/13\mathbb{Z} F13​=Z/13Z中， 1 ‾ 5 ‾ = a ‾ = − 5 ‾ = 8 ‾ \frac{\overline{1}}{\overline{5}}=\overline{a}=\overline{-5}=\overline{8} 51​=a=−5​=8

    定理: Z = K 0 ⋃ K 1 ⋃ ⋯ ⋃ K m − 1 ,   K i ⋂ K j = ∅ ( ∀ i ≠ j ) \mathbb{Z}={{K}_{0}}\bigcup {{K}_{1}}\bigcup \cdots \bigcup {{K}_{m-1}},\text{ }{{K}_{i}}\bigcap {{K}_{j}}=\varnothing \left( \forall i\ne j \right) Z=K0​⋃K1​⋃⋯⋃Km−1​, Ki​⋂Kj​=∅(∀i​=j)

    定理: 两个整数来自模 m m m同一个剩余类 ⇔ \Leftrightarrow ⇔两个数的差被 m m m整除。

    证明   不妨设该模 m m m同余类为 K r ( r ∈ { 0 , 1 , 2 , ⋯   , m − 1 } ) {{K}_{r}}\left( r\in \left\{ 0,1,2,\cdots ,m-1 \right\} \right) Kr​(r∈{0,1,2,⋯,m−1})。

    ( ⇒ ) \left( \Rightarrow \right) (⇒) ∀ a , b ∈ K r \forall a,b\in {{K}_{r}} ∀a,b∈Kr​， ∃ k a , k b ∈ Z ,   s . t . \exists {{k}_{a}},{{k}_{b}}\in \mathbb{Z},\text{ }s.t. ∃ka​,kb​∈Z, s.t. a = k a m + r b = k b m + r }   ⇒   ( a − b ) = ( k a − k b ) m   ⇒   m ∣ ( a − b ) \left. \begin{aligned} & a={{k}_{a}}m+r \\ & b={{k}_{b}}m+r \\ \end{aligned} \right\}\text{ }\Rightarrow \text{ }\left( a-b \right)=\left( {{k}_{a}}-{{k}_{b}} \right)m\text{ }\Rightarrow \text{ }\left. m \right|\left( a-b \right) ​a=ka​m+rb=kb​m+r​} ⇒ (a−b)=(ka​−kb​)m ⇒ m∣(a−b) ( ⇐ ) \left( \Leftarrow \right) (⇐) m ∣ ( a − b )   ⇒   ∃ k ∈ Z ,   s . t .   a − b = k m \left. m \right|\left( a-b \right)\text{ }\Rightarrow \text{ }\exists k\in \mathbb{Z},\text{ }s.t.\text{ }a-b=km m∣(a−b) ⇒ ∃k∈Z, s.t. a−b=km 若 b ∈ K r b\in {{K}_{r}} b∈Kr​，则 ∃ k b ∈ Z ,   s . t .   b = k b m + r \exists {{k}_{b}}\in \mathbb{Z},\text{ }s.t.\text{ }b={{k}_{b}}m+r ∃kb​∈Z, s.t. b=kb​m+r。代入上式得 a = b + k m = ( k b + k ) m + r   ⇒   a ∈ K r a=b+km=\left( {{k}_{b}}+k \right)m+r\text{ }\Rightarrow \text{ }a\in {{K}_{r}} a=b+km=(kb​+k)m+r ⇒ a∈Kr​

    定理: 若 p p p是素数，则 Z / p Z \mathbb{Z}/p\mathbb{Z} Z/pZ是一个域，记为 F p {{\mathbb{F}}_{p}} Fp​。

    证明   参见博文抽象代数练习（I）中的Hw8。

    定理: 若 m m m是合数， Z / m Z \mathbb{Z}/m\mathbb{Z} Z/mZ一定不是域。

    证明 m m m是合数 ⇒ \Rightarrow ⇒ ∃ a , b ∈ Z > 1 ,   s . t .   m = a b \exists a,b\in {{\mathbb{Z}}_{>1}},\text{ }s.t.\text{ }m=ab ∃a,b∈Z>1​, s.t. m=ab。 相应地，在 Z / m Z = { 0 ‾ , 1 ‾ , ⋯   , m − 1 ‾ } \mathbb{Z}/m\mathbb{Z}=\left\{ \overline{0},\overline{1},\cdots ,\overline{m-1} \right\} Z/mZ={0,1,⋯,m−1​}中，有 a ‾ ⋅ b ‾ = b ‾ ⋅ a ‾ = 0 ‾ \overline{a}\centerdot \overline{b}=\overline{b}\centerdot \overline{a}=\overline{0} a⋅b=b⋅a=0 若 Z / m Z \mathbb{Z}/m\mathbb{Z} Z/mZ是一个域，则对 a ‾ ∈ Z / m Z ,   \overline{a}\in \mathbb{Z}/m\mathbb{Z},\text{ } a∈Z/mZ,  ∃ c ‾ ∈ Z / m Z ,   s . t . \exists \overline{c}\in \mathbb{Z}/m\mathbb{Z},\text{ }s.t. ∃c∈Z/mZ, s.t.   a ‾ ⋅ c ‾ = 1 ‾ ⇒ ( b ‾ ⋅ a ‾ ) ⋅ c ‾ = b ‾ ⋅ 1 ‾ ⇒ 0 ‾ ⋅ c ‾ = b ‾ ⇒ 0 ‾ = b ‾ \begin{aligned} & \text{ }\overline{a}\centerdot \overline{c}=\overline{1} \\ & \Rightarrow \left( \overline{b}\centerdot \overline{a} \right)\centerdot \overline{c}=\overline{b}\centerdot \overline{1} \\ & \Rightarrow \overline{0}\centerdot \overline{c}=\overline{b} \\ & \Rightarrow \overline{0}=\overline{b} \\ \end{aligned} ​ a⋅c=1⇒(b⋅a)⋅c=b⋅1⇒0⋅c=b⇒0=b​ 这与 b ∈ Z > 1 b\in {{\mathbb{Z}}_{>1}} b∈Z>1​矛盾。由反证法，有 Z / m Z \mathbb{Z}/m\mathbb{Z} Z/mZ不是一个域。

    完全剩余系

    定义   设 { K 0 , K 1 , ⋯   , K m − 1 } \left\{ {{K}_{0}},{{K}_{1}},\cdots ,{{K}_{m-1}} \right\} {K0​,K1​,⋯,Km−1​}是模 m m m的剩余类环。若 a 0 ∈ K 0 ,   a 1 ∈ K 1 ,   ⋯   , a m − 1 ∈ K m − 1 {{a}_{0}}\in {{K}_{0}},\text{ }{{a}_{1}}\in {{K}_{1}},\text{ }\cdots ,{{a}_{m-1}}\in {{K}_{m-1}} a0​∈K0​, a1​∈K1​, ⋯,am−1​∈Km−1​，则称 a 0 , a 1 , ⋯   , a m − 1 {{a}_{0}},{{a}_{1}},\cdots ,{{a}_{m-1}} a0​,a1​,⋯,am−1​为模 m m m的完全剩余系==。若 x x x分别取 a 0 , a 1 , ⋯   , a m − 1 {{a}_{0}},{{a}_{1}},\cdots ,{{a}_{m-1}} a0​,a1​,⋯,am−1​每个元素且仅取一次，则称 x x x通过模 m m m的完全剩余系。

    例子

    0 , 1 , ⋯   , m − 1 0,1,\cdots ,m-1 0,1,⋯,m−1是模 m m m的完全剩余系，称为模 m m m的最小非负完全剩余系。 例如 0 , 1 0,1 0,1是模2的最小非负完全剩余系。

    若 m m m是偶数，则 − m 2 + 1 , ⋯   , − 1 , 0 , 1 , ⋯   , m 2 − m 2 , ⋯   , − 1 , 0 , 1 , ⋯   , m 2 − 1 \begin{aligned} & -\frac{m}{2}+1,\cdots ,-1,0,1,\cdots ,\frac{m}{2} \\ & -\frac{m}{2},\cdots ,-1,0,1,\cdots ,\frac{m}{2}-1 \\ \end{aligned} ​−2m​+1,⋯,−1,0,1,⋯,2m​−2m​,⋯,−1,0,1,⋯,2m​−1​ 都是模 m m m的完全剩余系。 若 m m m是奇数，则 − m − 1 2 , ⋯   , − 1 , 0 , 1 , ⋯   , m − 1 2 -\frac{m-1}{2},\cdots ,-1,0,1,\cdots ,\frac{m-1}{2} −2m−1​,⋯,−1,0,1,⋯,2m−1​ 是模 m m m的完全剩余系。 以上均称为模 m m m的绝对最小完全剩余系。 例如 − 3 , − 2 , − 1 , 0 , 1 , 2 − 2 , − 1 , 0 , 1 , 2 , 3 \begin{aligned} & -3,-2,-1,0,1,2 \\ & -2,-1,0,1,2,3 \\ \end{aligned} ​−3,−2,−1,0,1,2−2,−1,0,1,2,3​ 均为模 6 6 6的绝对最小完全剩余系。 − 3 , − 2 , − 1 , 0 , 1 , 2 , 3 -3,-2,-1,0,1,2,3 −3,−2,−1,0,1,2,3 是模 7 7 7的绝对最小完全剩余系。

    因为 0 , 1 , 2 , 3 0,1,2,3 0,1,2,3是模 4 4 4的完全剩余系， gcd ⁡ ( 3 , 4 ) = 1 \gcd \left( 3,4 \right)=1 gcd(3,4)=1，所以 3 × 0 + 0 ,   3 × 1 + 0 ,   3 × 2 + 0 ,   3 × 3 + 0 3\times 0+0,\text{ }3\times 1+0,\text{ }3\times 2+0,\text{ }3\times 3+0 3×0+0, 3×1+0, 3×2+0, 3×3+0即 0 , 3,6,9 0,\text{3,6,9} 0,3,6,9是模4的完全剩余系。 又因为 gcd ⁡ ( 4 , 5 ) = 1 \gcd \left( 4,5 \right)=1 gcd(4,5)=1 ，所以 5 × 0 + 1 ,  5 × 1 + 1 ,  5 × 2 + 1 ,  5 × 3 + 1 5\times 0+1,\text{ 5}\times 1+1,\text{ 5}\times 2+1,\text{ 5}\times 3+1 5×0+1, 5×1+1, 5×2+1, 5×3+1 即 1 , 6 , 11 , 16 1,6,11,16 1,6,11,16是模 4 4 4的完全剩余系。

    定理: m m m个整数作成模 m m m的一个完全剩余系 ⇔ \Leftrightarrow ⇔两两对模 m m m不同余。

    定理: 设 a 0 , a 1 , ⋯   , a m − 1 {{a}_{0}},{{a}_{1}},\cdots ,{{a}_{m-1}} a0​,a1​,⋯,am−1​是模 m m m的完全剩余系， gcd ⁡ ( a , m ) = 1 \gcd \left( a,m \right)=1 gcd(a,m)=1，则 a a 0 + b ,   a a 1 + b ,   ⋯   , a a m − 1 + b a{{a}_{0}}+b,\text{ }a{{a}_{1}}+b,\text{ }\cdots ,a{{a}_{m-1}}+b aa0​+b, aa1​+b, ⋯,aam−1​+b也是模 m m m的完全剩余系。

    证明   设 S = { K r : ∃ i ∈ { 0 , 1 , ⋯   , m − 1 } ,   s . t .   a a i + b ∈ K r } S=\left\{ {{K}_{r}}:\exists i\in \left\{ 0,1,\cdots ,m-1 \right\},\text{ }s.t.\text{ }a{{a}_{i}}+b\in {{K}_{r}} \right\} S={Kr​:∃i∈{0,1,⋯,m−1}, s.t. aai​+b∈Kr​} 则定理等价于证明 ∣ S ∣ = m \left| S \right|=m ∣S∣=m。

    由于 a 0 , a 1 , ⋯   , a m − 1 {{a}_{0}},{{a}_{1}},\cdots ,{{a}_{m-1}} a0​,a1​,⋯,am−1​是模 m m m的完全剩余系，因此 ∀ i , j ∈ { 0 , 1 , ⋯   , m − 1 } ,   i ≠ j \forall i,j\in \left\{ 0,1,\cdots ,m-1 \right\},\text{ }i\ne j ∀i,j∈{0,1,⋯,m−1}, i​=j， a i , a j {{a}_{i}},{{a}_{j}} ai​,aj​来自不同的剩余类，有 m ∣ ( a i − a j ) m\cancel{|}\left( {{a}_{i}}-{{a}_{j}} \right) m∣ ​(ai​−aj​)。 m ∣ ( a i − a j ) gcd ⁡ ( a , m ) = 1 }   ⇒   m ∣ a ( a i − a j ) = [ ( a a i + b ) − ( a a j + b ) ] \left. \begin{aligned} & m\cancel{|}\left( {{a}_{i}}-{{a}_{j}} \right) \\ & \gcd \left( a,m \right)=1 \\ \end{aligned} \right\}\text{ }\Rightarrow \text{ }m\cancel{|}a\left( {{a}_{i}}-{{a}_{j}} \right)=\left[ \left( a{{a}_{i}}+b \right)-\left( a{{a}_{j}}+b \right) \right] ​m∣ ​(ai​−aj​)gcd(a,m)=1​} ⇒ m∣ ​a(ai​−aj​)=[(aai​+b)−(aaj​+b)] 于是 ∀ i ≠ j , a a i + b ,   a a j + b \forall i\ne j,a{{a}_{i}}+b,\text{ }a{{a}_{j}}+b ∀i​=j,aai​+b, aaj​+b来自不同的剩余类，于是有 ∣ S ∣ ≥ ∣ { 0 , 1 , ⋯   , m − 1 } ∣ = m \left| S \right|\ge \left| \left\{ 0,1,\cdots ,m-1 \right\} \right|=m ∣S∣≥∣{0,1,⋯,m−1}∣=m。由于 ∀ i ≠ j ,   K i ⋂ K j = ∅ \forall i\ne j,\text{ }{{K}_{i}}\bigcap {{K}_{j}}=\varnothing ∀i​=j, Ki​⋂Kj​=∅，即 ∀ i ,   a a i + b \forall i,\text{ }a{{a}_{i}}+b ∀i, aai​+b只来源于一个剩余类，因此有 ∣ S ∣ ≤ ∣ { 0 , 1 , ⋯   , m − 1 } ∣ = m \left| S \right|\le \left| \left\{ 0,1,\cdots ,m-1 \right\} \right|=m ∣S∣≤∣{0,1,⋯,m−1}∣=m。因此有 ∣ S ∣ = m \left| S \right|=m ∣S∣=m。

    定理: 设 m 1 , m 2 ∈ Z ,  gcd ( m 1 , m 2 ) = 1 {{m}_{1}},{{m}_{2}}\in \mathbb{Z},\text{ gcd}\left( {{m}_{1}},{{m}_{2}} \right)=1 m1​,m2​∈Z, gcd(m1​,m2​)=1，设 x 1 {{x}_{1}} x1​通过模 m 1 {{m}_{1}} m1​的完全剩余系 K 1 K_1 K1​， x 2 {{x}_{2}} x2​通过模 m 2 {{m}_{2}} m2​的完全剩余系 K 2 K_2 K2​，则 m 1 x 2 + m 2 x 1 {{m}_{1}}{{x}_{2}}+{{m}_{2}}{{x}_{1}} m1​x2​+m2​x1​通过模 m 1 m 2 {{m}_{1}}{{m}_{2}} m1​m2​的完全剩余系 K K K。

    证明

    先证明 K K K中任意两个由不完全相同的 x 1 ∈ K 1 , x 2 ∈ K 2 {{x}_{1}}\in {{K}_{1}},{{x}_{2}}\in {{K}_{2}} x1​∈K1​,x2​∈K2​生成的元素不同余。 取 m 2 x 1 ′ + m 1 x 2 ′ , m 2 x 1 ′ ′ + m 1 x 2 ′ ′ ∈ K ,   x 1 ′ , x 1 ′ ′ ∈ K 1 ,   x 2 ′ , x 2 ′ ′ ∈ K 2 {{m}_{2}}{{x}_{1}}'+{{m}_{1}}{{x}_{2}}',{{m}_{2}}{{x}_{1}}''+{{m}_{1}}{{x}_{2}}''\in K,\text{ }{{x}_{1}}',{{x}_{1}}''\in {{K}_{1}},\text{ }{{x}_{2}}',{{x}_{2}}''\in {{K}_{2}} m2​x1​′+m1​x2​′,m2​x1​′′+m1​x2​′′∈K, x1​′,x1​′′∈K1​, x2​′,x2​′′∈K2​，若 m 2 x 1 ′ + m 1 x 2 ′ ≡ m 2 x 1 ′ ′ + m 1 x 2 ′ ′ (   m o d   m 1 m 2 ) {{m}_{2}}{{x}_{1}}'+{{m}_{1}}{{x}_{2}}'\equiv {{m}_{2}}{{x}_{1}}''+{{m}_{1}}{{x}_{2}}''\left( \bmod {{m}_{1}}{{m}_{2}} \right) m2​x1​′+m1​x2​′≡m2​x1​′′+m1​x2​′′(modm1​m2​) 由 m 1 ∣ m 1 m 2 \left. {{m}_{1}} \right|{{m}_{1}}{{m}_{2}} m1​∣m1​m2​和初等数论 课堂笔记 第三章 --同余及其一些有趣的应用其中的同余性质壬有 m 2 x 1 ′ + m 1 x 2 ′ ≡ m 2 x 1 ′ ′ + m 1 x 2 ′ ′ (   m o d   m 1 ) {{m}_{2}}{{x}_{1}}'+{{m}_{1}}{{x}_{2}}'\equiv {{m}_{2}}{{x}_{1}}''+{{m}_{1}}{{x}_{2}}''\left( \bmod {{m}_{1}} \right) m2​x1​′+m1​x2​′≡m2​x1​′′+m1​x2​′′(modm1​) 又 m 1 x 2 ′ ≡ 0 (   m o d   m 1 ) ,   m 1 x 2 ′ ′ ≡ 0 (   m o d   m 1 ) {{m}_{1}}{{x}_{2}}'\equiv 0\left( \bmod {{m}_{1}} \right),\text{ }{{m}_{1}}{{x}_{2}}''\equiv 0\left( \bmod {{m}_{1}} \right) m1​x2​′≡0(modm1​), m1​x2​′′≡0(modm1​)，因此有 m 2 x 1 ′ + 0 ≡ m 2 x 1 ′ + m 1 x 2 ′ ≡ m 2 x 1 ′ ′ + m 1 x 2 ′ ′ ≡ m 2 x 1 ′ ′ + 0 (   m o d   m 1 ) ⇒ m 2 x 1 ′ ≡ m 2 x 1 ′ ′ (   m o d   m 1 ) \begin{aligned} & {{m}_{2}}{{x}_{1}}'+0\equiv {{m}_{2}}{{x}_{1}}'+{{m}_{1}}{{x}_{2}}'\equiv {{m}_{2}}{{x}_{1}}''+{{m}_{1}}{{x}_{2}}''\equiv {{m}_{2}}{{x}_{1}}''+0\left( \bmod {{m}_{1}} \right) \\ & \Rightarrow {{m}_{2}}{{x}_{1}}'\equiv {{m}_{2}}{{x}_{1}}''\left( \bmod {{m}_{1}} \right) \\ \end{aligned} ​m2​x1​′+0≡m2​x1​′+m1​x2​′≡m2​x1​′′+m1​x2​′′≡m2​x1​′′+0(modm1​)⇒m2​x1​′≡m2​x1​′′(modm1​)​ 同理可得 m 1 x 2 ′ ≡ m 1 x 2 ′ ′ (   m o d   m 2 ) {{m}_{1}}{{x}_{2}}'\equiv {{m}_{1}}{{x}_{2}}''\left( \bmod {{m}_{2}} \right) m1​x2​′≡m1​x2​′′(modm2​) 由 ( m 1 , m 2 ) = 1 \left( {{m}_{1}},{{m}_{2}} \right)=1 (m1​,m2​)=1和初等数论 课堂笔记 第三章 --同余及其一些有趣的应用其中的同余性质己有 x 1 ′ ≡ x 1 ′ ′ (   m o d   m 1 ) x 2 ′ ≡ x 2 ′ ′ (   m o d   m 2 ) \begin{aligned} & {{x}_{1}}'\equiv {{x}_{1}}''\left( \bmod {{m}_{1}} \right) \\ & {{x}_{2}}'\equiv {{x}_{2}}''\left( \bmod {{m}_{2}} \right) \\ \end{aligned} ​x1​′≡x1​′′(modm1​)x2​′≡x2​′′(modm2​)​ 由于 x 1 ′ , x 1 ′ ′ ∈ K 1 ,   x 2 ′ , x 2 ′ ′ ∈ K 2 {{x}_{1}}',{{x}_{1}}''\in {{K}_{1}},\text{ }{{x}_{2}}',{{x}_{2}}''\in {{K}_{2}} x1​′,x1​′′∈K1​, x2​′,x2​′′∈K2​，因此可推得 x 1 ′ = x 1 ′ ′ x 2 ′ = x 2 ′ ′ \begin{aligned} & {{x}_{1}}'={{x}_{1}}'' \\ & {{x}_{2}}'={{x}_{2}}'' \\ \end{aligned} ​x1​′=x1​′′x2​′=x2​′′​ 这表明若 x 1 ′ , x 2 ′ {{x}_{1}}',{{x}_{2}}' x1​′,x2​′与 x 1 ′ ′ , x 2 ′ ′ {{x}_{1}}'',{{x}_{2}}'' x1​′′,x2​′′不完全相同，则有 m 2 x 1 ′ + m 1 x 2 ′ ≢ m 2 x 1 ′ ′ + m 1 x 2 ′ ′ (   m o d   m 1 ) {{m}_{2}}{{x}_{1}}'+{{m}_{1}}{{x}_{2}}'\not{\equiv }{{m}_{2}}{{x}_{1}}''+{{m}_{1}}{{x}_{2}}''\left( \bmod {{m}_{1}} \right) m2​x1​′+m1​x2​′​≡m2​x1​′′+m1​x2​′′(modm1​) 即证得 K K K中任意两个由不完全相同的 x 1 ∈ K 1 , x 2 ∈ K 2 {{x}_{1}}\in {{K}_{1}},{{x}_{2}}\in {{K}_{2}} x1​∈K1​,x2​∈K2​生成的元素不同余。 K K K中任意两个由不完全相同的 x 1 ∈ K 1 , x 2 ∈ K 2 {{x}_{1}}\in {{K}_{1}},{{x}_{2}}\in {{K}_{2}} x1​∈K1​,x2​∈K2​生成的元素不同余，因此这两个元素也不可能相等。在此基础上，有 ∣ K ∣ = ∣ K 1 ∣ × ∣ K 2 ∣ = m 1 m 2 \left| K \right|=\left| {{K}_{1}} \right|\times \left| {{K}_{2}} \right|={{m}_{1}}{{m}_{2}} ∣K∣=∣K1​∣×∣K2​∣=m1​m2​综上， K K K是模 m 1 m 2 {{m}_{1}}{{m}_{2}} m1​m2​的完全剩余系。

    推广: 若 m 1 , m 2 , ⋯   , m k {{m}_{1}},{{m}_{2}},\cdots ,{{m}_{k}} m1​,m2​,⋯,mk​是 k k k个两两互素的正整数， x 1 , x 2 ⋯   , x k {{x}_{1}},{{x}_{2}}\cdots ,{{x}_{k}} x1​,x2​⋯,xk​分别通过模 m 1 , m 2 , ⋯   , m k {{m}_{1}},{{m}_{2}},\cdots ,{{m}_{k}} m1​,m2​,⋯,mk​的完全剩余系，则 M 1 x 1 + M 2 x 2 + ⋯ + M k x k {{M}_{1}}{{x}_{1}}+{{M}_{2}}{{x}_{2}}+\cdots +{{M}_{k}}{{x}_{k}} M1​x1​+M2​x2​+⋯+Mk​xk​通过模 m 1 m 2 ⋯ m k = m {{m}_{1}}{{m}_{2}}\cdots {{m}_{k}}=m m1​m2​⋯mk​=m的完全剩余系，其中 m = m i M i ,   i = 1 , 2 , ⋯   , k m={{m}_{i}}{{M}_{i}},\text{ }i=1,2,\cdots ,k m=mi​Mi​, i=1,2,⋯,k。

    证明   分别设模 m 1 , m 2 , ⋯   , m k {{m}_{1}},{{m}_{2}},\cdots ,{{m}_{k}} m1​,m2​,⋯,mk​的完全剩余系是 K 1 , K 2 , ⋯   , K k {{K}_{1}},{{K}_{2}},\cdots ,{{K}_{k}} K1​,K2​,⋯,Kk​。 ∀ x i ′ , x i ′ ′ ∈ K i ,   i = 1 , 2 , ⋯   , k \forall {{x}_{i}}',{{x}_{i}}''\in {{K}_{i}},\text{ }i=1,2,\cdots ,k ∀xi​′,xi​′′∈Ki​, i=1,2,⋯,k，考虑以下式子 M 1 x 1 ′ + M 2 x 2 ′ + ⋯ + M k x k ′ ≡ M 1 x 1 ′ ′ + M 2 x 2 ′ ′ + ⋯ + M k x k ′ ′ (   m o d   m 1 m 2 ⋯ m k = m ) {{M}_{1}}{{x}_{1}}'+{{M}_{2}}{{x}_{2}}'+\cdots +{{M}_{k}}{{x}_{k}}'\equiv {{M}_{1}}{{x}_{1}}''+{{M}_{2}}{{x}_{2}}''+\cdots +{{M}_{k}}{{x}_{k}}''\left( \bmod {{m}_{1}}{{m}_{2}}\cdots {{m}_{k}}=m \right) M1​x1​′+M2​x2​′+⋯+Mk​xk​′≡M1​x1​′′+M2​x2​′′+⋯+Mk​xk​′′(modm1​m2​⋯mk​=m) 由于 m 1 ∣ m \left. {{m}_{1}} \right|m m1​∣m，因此有 M 1 x 1 ′ + M 2 x 2 ′ + ⋯ + M k x k ′ ≡ M 1 x 1 ′ ′ + M 2 x 2 ′ ′ + ⋯ + M k x k ′ ′ (   m o d   m 1 ) {{M}_{1}}{{x}_{1}}'+{{M}_{2}}{{x}_{2}}'+\cdots +{{M}_{k}}{{x}_{k}}'\equiv {{M}_{1}}{{x}_{1}}''+{{M}_{2}}{{x}_{2}}''+\cdots +{{M}_{k}}{{x}_{k}}''\left( \bmod {{m}_{1}} \right) M1​x1​′+M2​x2​′+⋯+Mk​xk​′≡M1​x1​′′+M2​x2​′′+⋯+Mk​xk​′′(modm1​) 由于 m = m i M i m={{m}_{i}}{{M}_{i}} m=mi​Mi​，因此 ∀ i ∈ { 2 , 3 , ⋯   , k } \forall i\in \left\{ 2,3,\cdots ,k \right\} ∀i∈{2,3,⋯,k}，有 M i x i ′ ≡ M i x i ′ ′ ≡ 0 (   m o d   m 1 ) {{M}_{i}}{{x}_{i}}'\equiv {{M}_{i}}{{x}_{i}}''\equiv 0\left( \bmod {{m}_{1}} \right) Mi​xi​′≡Mi​xi​′′≡0(modm1​)，于是有 M 1 x 1 ′ ≡ M 1 x 1 ′ ′ (   m o d   m 1 ) {{M}_{1}}{{x}_{1}}'\equiv {{M}_{1}}{{x}_{1}}''\left( \bmod {{m}_{1}} \right) M1​x1​′≡M1​x1​′′(modm1​) 由于 m 1 , m 2 , ⋯   , m k {{m}_{1}},{{m}_{2}},\cdots ,{{m}_{k}} m1​,m2​,⋯,mk​两两互素， M 1 = m 2 m 3 ⋯ m k {{M}_{1}}={{m}_{2}}{{m}_{3}}\cdots {{m}_{k}} M1​=m2​m3​⋯mk​，因此有 gcd ⁡ ( m 1 , M 1 ) = 1 \gcd \left( {{m}_{1}},{{M}_{1}} \right)=1 gcd(m1​,M1​)=1。因此有 x 1 ′ ≡ x 1 ′ ′ (   m o d   m 1 ) {{x}_{1}}'\equiv {{x}_{1}}''\left( \bmod {{m}_{1}} \right) x1​′≡x1​′′(modm1​) 由于 x 1 ′ , x 1 ′ ′ {{x}_{1}}',{{x}_{1}}'' x1​′,x1​′′来自于模 m 1 {{m}_{1}} m1​的同一个完全剩余系 K 1 {{K}_{1}} K1​， K 1 {{K}_{1}} K1​里面任意两个不同的数之间对 m 1 {{m}_{1}} m1​不同余，于是有 x 1 ′ = x 1 ′ ′ {{x}_{1}}'={{x}_{1}}'' x1​′=x1​′′ 同理可推得 x 2 ′ = x 2 ′ ′ ,   x 3 ′ = x 3 ′ ′ ,   ⋯   ,   x k ′ = x k ′ ′ {{x}_{2}}'={{x}_{2}}'',\text{ }{{x}_{3}}'={{x}_{3}}'',\text{ }\cdots ,\text{ }{{x}_{k}}'={{x}_{k}}'' x2​′=x2​′′, x3​′=x3​′′, ⋯, xk​′=xk​′′ 于是有 ( x 1 ′ , x 2 ′ , ⋯   , x k ′ ) ≠ ( x 1 ′ ′ , x 2 ′ ′ , ⋯   , x k ′ ′ )   ⇒   ∑ i = 1 k M i x i ′ ≡ ∑ i = 1 k M i x i ′ ′ (   m o d   m ) \left( {{x}_{1}}',{{x}_{2}}',\cdots ,{{x}_{k}}' \right)\ne \left( {{x}_{1}}'',{{x}_{2}}'',\cdots ,{{x}_{k}}'' \right)\text{ }\Rightarrow \text{ }\sum\limits_{i=1}^{k}{{{M}_{i}}{{x}_{i}}'}\cancel{\equiv }\sum\limits_{i=1}^{k}{{{M}_{i}}{{x}_{i}}''}\left( \bmod m \right) (x1​′,x2​′,⋯,xk​′)​=(x1​′′,x2​′′,⋯,xk​′′) ⇒ i=1∑k​Mi​xi​′≡ ​i=1∑k​Mi​xi​′′(modm) 设模 m m m的完全剩余系是 K K K。也就有 ∣ K ∣ = ∏ i = 1 k ∣ K i ∣ \left| K \right|=\prod\limits_{i=1}^{k}{\left| {{K}_{i}} \right|} ∣K∣=i=1∏k​∣Ki​∣ 因此 M 1 x 1 + M 2 x 2 + ⋯ + M k x k {{M}_{1}}{{x}_{1}}+{{M}_{2}}{{x}_{2}}+\cdots +{{M}_{k}}{{x}_{k}} M1​x1​+M2​x2​+⋯+Mk​xk​通过模 m m m的完全剩余系。

    Processed: 0.014, SQL: 9