基本概念和一次同余式

基本概念

同余式的定义：设m∈Z+,f(x)=anxn+an−1xn−1+....+a1x+a0,ai∈Zm\in Z_{+},f(x)=a_nx_n+a_{n-1}x^{n-1}+....+a_{1}x+a_0,a_i\in Z，则f(x)≡0( mod m)f(x)\equiv0(~mod~m)叫做模m的同余式，若ai≢0 (mod m)a_i\not\equiv 0~(mod~m)，则n叫做上述同余式的次数。

同余式解的定义：若a是使得f(a)≡0 (mod m)f(a)\equiv0~(mod~m)成立的一个整数，则称a所在的模m的剩余类kak_a为同余式的一个解(一类解)，记为x≡a (mod m)x\equiv a~(mod~m)

一次同余式

一次同余式：形如ax≡b (mod m)ax\equiv b~(mod~m)，且满足a≢0 (mod m)a\not\equiv 0~(mod~m)，这样形式的式子称为一次同余式。

定理1：一次同余式ax≡b (mod m),a≢0 (mod m)  ax\equiv b~(mod~m),a\not\equiv 0~(mod~m)~~当(a,m)=1(a,m)=1时有唯一解。即当未知数系数与模数互质的时候有唯一解。

定理2：设(a,m)=d(a,m)=d，则一次同余式ax≡b (mod m),a≢0 (mod m)  ax\equiv b~(mod~m),a\not\equiv 0~(mod~m)~~,有解的充分必要条件是d∣bd\mid b，当该同余式有解时，它恰好有d个解

解一次同余方程

  • 熟悉完定理1和定理2的推导过程，其实可以了解到解一次同余方程其实就是解不定方程。下面俩个例题给出解同余方程的步骤。

求解同余方程步骤：

  1. 先求解gcd(a,m)gcd(a,m)，判断a和m是否互素。当gcd(a,m)gcd(a,m)互素可以得到该方程有唯一解，当不互素的时候令gcd(a,m)=dgcd(a,m)=d，判断d是否能整除b，能整除就说明有d个解，不能整除就说明该同余方程无解
  2. 当gcd(a,m)=1gcd(a,m)=1时，直接去解二元不定方程as+mt=1as+mt=1，求出s，得到唯一解为x≡bs mod( m)x\equiv bs~mod(~m)，就结束了。
  3. **当gcd(a,m)=dgcd(a,m)=d**并且同余方程有解时，我们就要将题目所给的同余方程中的a、b、m都除以d，得到一个唯一解的同余方程a1x≡b1 mod( m1)a_1x\equiv b_1~mod(~m_1)，通过解二元不定方程as+mt=1as+mt=1，求出s，得到a1x≡b1 mod( m1)a_1x\equiv b_1~mod(~m_1)唯一解x≡b1s mod( m1)x\equiv b_1s~mod(~m_1)
  4. 求出原同余方程ax≡b mod( m)ax\equiv b~mod(~m)的解，其解为x≡b1s+km1 mod( m),k=0,1,...,d−1x\equiv b_1s + km_1~mod(~m),k=0,1,...,d-1

例题1：求一次同余方程2x≡3 (mod 5)2x\equiv 3~(mod~5)的所有解

例题2：求一次同余方程4x≡6(mod 10)4x\equiv 6(mod~10)的所有解

中国剩余定理(CRT)

中国剩余定理的个人认为算是基础部分最重要的一个定理，也是密码学中非常重要的一个定理。而二次互反律则是整个初等数论最重要的定理(听b站某位老师说的)。

  • 中国剩余定理是用来解同余方程组的，该同余方程组形式如下，特征有三个：
    • 未知数只有一个x
    • 每个同余式的模数不一样，但是一般要满足gcd(m1,m2,...,mk)=1才有解，否则需要使用拓展中国剩余定理
    • 每个同余式中b的值可以一样，也可以不一样

{x≡b1( mod m1)x≡b2( mod m2)............x≡bk( mod mk)                             (1)\begin{cases} x \equiv b_1(~mod~m_1)\\ x \equiv b_2(~mod~m_2)\\ ............\\ x \equiv b_k(~mod~m_k) \end{cases}~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(1)

  • 先来说解法再说其相关定理,这里默认gcd(m1,m2,...,mk)=1gcd(m_1,m_2,...,m_k)=1，按照从左到右的顺序计算出如下数据。
除数 余数 除数最小公倍数 衍数 乘率 各总
m1m_1 b1b_1 m1∗m2....mk=mm_1*m_2....m_k=m M1=mm1M_1=\frac{m}{m_1} y1=M1−1 (mod m1)y_1=M_1^{-1}~(mod~m_1) b1∗M1∗y1b_1*M_1*y_1
m2m_2 b2b_2 m1∗m2....mk=mm_1*m_2....m_k=m M2=mm2M_2=\frac{m}{m_2} y2=M2−1 (mod m2)y_2=M_2^{-1}~(mod~m_2) b2∗M2∗y2b_2*M_2*y_2
… … m1∗m2....mk=mm_1*m_2....m_k=m … …
mkm_k bkb_k m1∗m2....mk=mm_1*m_2....m_k=m Mk=mmkM_k=\frac{m}{m_k} yk=Mk−1 (mod mk)y_k=M_k^{-1}~(mod~m_k) bk∗Mk∗y3b_k*M_k*y_3
  • 最后得到最终结果：

x≡b1∗M1∗y1+b2∗M2∗y2+....+bk∗Mk∗yk mod( m)x\equiv b_1*M_1*y_1 + b_2*M_2*y_2+....+b_k*M_k*y_k~mod(~m)

定理1(中国剩余定理):

设m1,m2,...,mkm_1,m_2,...,m_k是k个两两互素的正整数，m=m1m2...mk,m=miMi(i=1,2,...,k)m=m_1m_2...m_k,m=m_iM_i(i=1,2,...,k)，则同余式组(1)的解为：

x≡M1′M1b1+M2′M2b2+....+Mk′Mkbk      (2)x\equiv M_1'M_1b_1+M_2'M_2b_2+....+M_k'M_kb_k~~~~~~(2)

其中Mi′Mi≡1( mod mi),i=1,2,...,kM_i'M_i\equiv1(~mod~m_i),i=1,2,...,k

定理2：

若b1,b2,...,bkb_1,b_2,...,b_k分别过模m1,m2,...,mkm_1,m_2,...,m_k的完全剩余系，则(2)过模m=m1m2...mkm=m_1m_2...m_k的完全剩余系。

高次同余式的解数及解法

素数模的同余式

定理1：

设p是素数，则同余式f(x)=anxn+an−1xn−1+...+a0≡0( mod p),an≢0 mod( p)f(x)=a_nx^{n}+a_{n-1}x^{n-1}+...+a_0 \equiv 0(~mod~p),a_n\not\equiv 0~mod(~p)，与一个次数不超过p-1的素数模p同余式等价。