2021-01-02

4.4 求解同余方程

线性同余方程

a x ≡ b   ( m o d   m ) , 其 中 , m ∈ N + , a , b ∈ N , x 为 变 量 , 这 样 的 方 程 称 为 线 性 同 余 方 程 ax \equiv b\ (mod\ m),其中,m \in {N}^{+},a,b \in N,x为变量,这样的方程称为线性同余方程 ax≡b (mod m),其中,m∈N+,a,b∈N,x为变量,这样的方程称为线性同余方程

首先,这是个方程,所以x是变量,剩下的就是在确定a,b,m的值之后,确定x的可选值有哪些。解题思路是这样的:
g c d ( a , m ) = 1 , 且 a , m ∈ N , 则 必 然 存 在 一 个 数 : a ‾ , 称 为 a 模 m 的 逆 , 能 够 使 得 a ⋅ a ‾ ≡ 1 ( m o d   m ) 。 gcd(a,m)=1,且 a,m \in N,则必然存在一个数:\overline{a},称为a模m的逆,能够使得 a \cdot \overline{a} \equiv 1 (mod\ m)。 gcd(a,m)=1,且a,m∈N,则必然存在一个数:a,称为a模m的逆,能够使得a⋅a≡1(mod m)。
这里先举一个现实的例子:
假 设 a = 3 , m = 7 , 则 − 2 ⋅ 3 ≡ 1 ( m o d   7 ) 假设 a=3,m=7,则 -2 \cdot 3 \equiv 1 (mod\ 7) 假设a=3,m=7,则−2⋅3≡1(mod 7)
在上面的基础之上,再来看下面的推论,让我们先假定这个逆一定存在(接下来会证明这个值一定存在)。这个值如何帮助我们解决最开始的问题呢?
∵ a x ≡ b   ( m o d   m ) a ⋅ a ‾ ⋅ x ≡ b ⋅ a ‾   ( m o d   m ) a ⋅ a ‾ ⋅ x   m o d   m = ( ( a ⋅ a ‾   m o d   m ) × ( x   m o d   m ) )   m o d   m a ⋅ a ‾ ≡ 1   ( m o d   m ) x   m o d   m = b ⋅ a ‾ m o d    m ∴ x ≡ b ⋅ a ‾ ( m o d    m ) \because ax \equiv b\ (mod\ m) \\ a \cdot \overline{a} \cdot x \equiv b \cdot \overline{a}\ (mod\ m) \\ a \cdot \overline{a} \cdot x\ mod\ m = ((a \cdot \overline{a}\ mod\ m) \times (x\ mod\ m))\ mod\ m \\ a \cdot \overline{a} \equiv 1\ (mod\ m) \\ x\ mod\ m = b \cdot \overline{a} \mod m \\ \therefore x \equiv b \cdot \overline{a}(\mod m) ∵ax≡b (mod m)a⋅a⋅x≡b⋅a (mod m)a⋅a⋅x mod m=((a⋅a mod m)×(x mod m)) mod ma⋅a≡1 (mod m)x mod m=b⋅amodm∴x≡b⋅a(modm)
这样就能获得了x的表达式。

那么问题就来了:

  1. a模m的逆一定存在吗?
  2. 如果存在,如何计算呢?

先是证明这个值一定存在。
∵ g c d ( a , m ) = 1 ∴ ∃ s , t , a s + t m = 1 ∴ ( a s + t m ) ≡ 1 ( m o d   m ) ( a s + t m ) ( m o d   m ) = ( ( a s   m o d   m ) + ( t m   m o d   m ) )   m o d   m ∵ t m   m o d   m = 0 ∴ ( a s ) ≡ 1 ( m o d   m ) , 这 里 s 就 是 作 为 a 的 逆 存 在 , 因 为 s 一 定 存 在 , 所 以 a ‾ 一 定 存 在 \because gcd(a,m)=1\\ \therefore \exists s,t,as+tm=1 \\ \therefore (as+tm) \equiv 1 (mod\ m) \\ (as+tm)(mod\ m)=((as\ mod\ m)+(tm\ mod\ m))\ mod\ m \\ \because tm\ mod\ m=0 \\ \therefore (as)\equiv 1 (mod\ m),这里s就是作为a的逆存在,因为s一定存在,所以 \overline{a} 一定存在 ∵gcd(a,m)=1∴∃s,t,as+tm=1∴(as+tm)≡1(mod m)(as+tm)(mod m)=((as mod m)+(tm mod m)) mod m∵tm mod m=0∴(as)≡1(mod m),这里s就是作为a的逆存在,因为s一定存在,所以a一定存在
接着就是这个值如何求,其实就是求贝祖系数

比如这里的
线 性 同 余 方 程 : 3 x ≡ 4   ( m o d    7 ) 的 解 是 什 么 ? 线性同余方程:3x \equiv 4\ (\mod 7) 的解是什么? 线性同余方程:3x≡4 (mod7)的解是什么?
解题过程:
∵ 5 ⋅ 3 − 2 ⋅ 7 = 1 ∴ x ≡ 5 ⋅ 4 ( m o d    7 ) ≡ 6 ( m o d    7 ) \because 5 \cdot 3 - 2 \cdot 7=1 \\ \therefore x \equiv 5 \cdot 4 (\mod 7) \equiv 6 (\mod 7) ∵5⋅3−2⋅7=1∴x≡5⋅4(mod7)≡6(mod7)
当然,答案不止一个,因为
− 8 ≡ 6 ( m o d    7 ) , 所 以 上 面 也 可 以 写 成 x ≡ − 8 ( m o d    7 ) -8 \equiv 6(\mod 7),所以上面也可以写成 x \equiv -8 (\mod 7) −8≡6(mod7),所以上面也可以写成x≡−8(mod7)

中国剩余定理:多个同余方程组

上面介绍了一个线性方程组的解,但是如果有多个线性方程组的解需要整合时,该怎么处理呢?

比如:
x ≡ 2 ( m o d    3 ) x ≡ 3 ( m o d    5 ) x ≡ 2 ( m o d    7 ) x \equiv 2(\mod 3)\\ x \equiv 3(\mod 5)\\ x \equiv 2(\mod 7) x≡2(mod3)x≡3(mod5)x≡2(mod7)
问,这个时候如何求解?

暂时先不管上面的具体问题,我们把上面的方程组类比成下面的形式:
x ≡ a 1 ( m o d    m 1 ) x ≡ a 2 ( m o d    m 2 ) ⋮ x ≡ a n ( m o d    m n ) 且 g c d ( m i , m j ) = 1 x \equiv {a}_{1}(\mod {m}_{1}) \\ x \equiv {a}_{2}(\mod {m}_{2}) \\ \vdots \\ x \equiv {a}_{n}(\mod {m}_{n}) \\ 且 gcd({m}_{i},{m}_{j})=1 x≡a1​(modm1​)x≡a2​(modm2​)⋮x≡an​(modmn​)且gcd(mi​,mj​)=1
解:
令 M k = m 1 × m 1 ⋯ m n m k , 令 y k 为   y k ≡ M k ( m o d    m k ) , 即 y k 为 M k 模 m k 的 逆 则 x = a 1 M 1 y 1 + a 2 M 2 y 2 ⋯ a n M n y n 令 {M}_{k}=\frac{ {m}_{1} \times {m}_{1} \cdots {m}_{n} }{ {m}_{k} },令{y}_{k}为\ {y}_{k} \equiv {M}_{k} (\mod {m}_{k}),即 {y}_{k}为 {M}_{k}模{m}_{k}的逆 \\ 则 x = {a}_{1}{M}_{1}{y}_{1}+{a}_{2}{M}_{2}{y}_{2} \cdots {a}_{n}{M}_{n}{y}_{n} 令Mk​=mk​m1​×m1​⋯mn​​,令yk​为 yk​≡Mk​(modmk​),即yk​为Mk​模mk​的逆则x=a1​M1​y1​+a2​M2​y2​⋯an​Mn​yn​
首先说明为什么上面的这种解法有效:
∵ ( a 1 M 1 y 1 + a 2 M 2 y 2 ⋯ a n M n y n )   m o d   m j = ( ( a 1 M 1 y 1 m o d    m j ) + ( a 2 M 2 y 2 m o d    m j ) ⋯ ( a n M n y n m o d    m j ) ) ( m o d   m j ) 当 n ≠ j 时 , M n ≡ 0 ( m o d    m j ) , 因 为 M n 中 有 m j , 所 以 上 面 可 以 化 简 为 a j M j y j m o d    m j 同 时 , ( ( a j m o d    m j ) ( M j y j m o d    m j ) ) ( m o d   m j ) 可 以 化 简 为 a j m o d    m j ∴ x = a j m o d    m j \because ({a}_{1}{M}_{1}{y}_{1}+{a}_{2}{M}_{2}{y}_{2} \cdots {a}_{n}{M}_{n}{y}_{n})\ mod\ {m}_{j}= (({a}_{1}{M}_{1}{y}_{1} \mod {m}_{j})+({a}_{2}{M}_{2}{y}_{2} \mod {m}_{j}) \cdots ({a}_{n}{M}_{n}{y}_{n} \mod {m}_{j}))(mod\ {m}_{j}) \\ 当 n \neq j时,{M}_{n} \equiv 0 (\mod {m}_{j}),因为{M}_{n}中有{m}_{j},所以上面可以化简为 \\ {a}_{j}{M}_{j}{y}_{j} \mod {m}_{j} \\ 同时,(({a}_{j} \mod {m}_{j})({M}_{j}{y}_{j} \mod {m}_{j}))(mod\ {m}_{j}) 可以化简为 \\ {a}_{j} \mod {m}_{j} \\ \therefore x={a}_{j} \mod {m}_{j} ∵(a1​M1​y1​+a2​M2​y2​⋯an​Mn​yn​) mod mj​=((a1​M1​y1​modmj​)+(a2​M2​y2​modmj​)⋯(an​Mn​yn​modmj​))(mod mj​)当n​=j时,Mn​≡0(modmj​),因为Mn​中有mj​,所以上面可以化简为aj​Mj​yj​modmj​同时,((aj​modmj​)(Mj​yj​modmj​))(mod mj​)可以化简为aj​modmj​∴x=aj​modmj​
然后上面可以得到一个x的值,但是我们看上面,我们可以得出,其实x可以写成
令 M = l c m ( m 1 , m 2 , m 3 ⋯ m n ) , d = x m o d M , 则 x = d   ( m o d   M ) 令M=lcm({m}_{1},{m}_{2},{m}_{3} \cdots {m}_{n}),d=x mod M,则 \\ x=d\ (mod\ M) 令M=lcm(m1​,m2​,m3​⋯mn​),d=xmodM,则x=d (mod M)

lcm,最小公倍数,定义见这里

具体例子见书上248页的例5.

大整数的计算机算术

这一章简单来说就是如何通过减少值来加快计算速度,比如让你计算1+3的速度总是快过10000+30000。说具体的计算方法前,书上的原话


m = m 1 × m 2 ⋯ m n , 且 g c d ( m i , m j ) = 1 , 则 一 个 0 < = a < = m 的 整 数 是 否 可 以 唯 一 表 示 成 ( a m o d    m 1 , a m o d    m 2 , a m o d    m 3 , ⋯ a m o d    m n ) m={m}_{1} \times {m}_{2} \cdots {m}_{n},且 gcd({m}_{i},{m}_{j})=1,\\ 则一个0<=a<=m的整数是否可以唯一表示成 (a\mod {m}_{1},a\mod {m}_{2},a\mod {m}_{3}, \cdots a\mod {m}_{n}) m=m1​×m2​⋯mn​,且gcd(mi​,mj​)=1,则一个0<=a<=m的整数是否可以唯一表示成(amodm1​,amodm2​,amodm3​,⋯amodmn​)

这样表示肯定没有问题的,因为在上面的中国剩余定理中我们证明了这样的数字是肯定存在的,至于在0~m之间是否唯一的问题了,在上面的最后我们也证明了这样的x的值是唯一的。

或者换个角度思考这个问题。

2021-01-02

这样的数字差一点都不行:

2021-01-02

例子:

将 123684和413456的加法转换成100内的加减

∵ 这 里 选 择 100 以 内 的 4 个 数 99 , 98 , 97 , 95 123684 m o d    99 = 33 , 123684 m o d    98 = 8 , 123684 m o d    97 = 9 , 123684 m o d    95 = 89 , 所 以 将 123684 改 写 成 ( 33 , 98 , 97 , 95 ) 同 理 413456 改 写 成 ( 32 , 92 , 42 , 16 ) \because 这里选择100以内的4个数 99,98,97,95 \\ 123684 \mod 99=33 ,123684 \mod 98=8,123684 \mod 97=9,123684 \mod 95=89,所以将 123684 改写成 (33,98,97,95) \\ 同理 413456 改写成 (32,92,42,16) ∵这里选择100以内的4个数99,98,97,95123684mod99=33,123684mod98=8,123684mod97=9,123684mod95=89,所以将123684改写成(33,98,97,95)同理413456改写成(32,92,42,16)

然后12368+413456可以归纳为
( ( 33 + 32 ) m o d    99 , ( 98 + 92 ) m o d    98 , ( 97 + 42 ) m o d    97 , ( 95 + 16 ) m o d    95 ) 即 ( 65 , 2 , 51 , 10 ) ((33+32)\mod 99,(98+92)\mod 98,(97+42)\mod 97,(95+16)\mod 95) \\ 即\\ (65,2,51,10) ((33+32)mod99,(98+92)mod98,(97+42)mod97,(95+16)mod95)即(65,2,51,10)
上面计算的原理见这里的同余种的公式

然后如果要原始的值,需要计算
x ≡ 65 ( m o d   99 ) x ≡ 2 ( m o d   98 ) x ≡ 51 ( m o d   97 ) x ≡ 10 ( m o d   95 ) x \equiv 65 (mod\ 99) \\ x \equiv 2 (mod\ 98) \\ x \equiv 51 (mod\ 97) \\ x \equiv 10 (mod\ 95) x≡65(mod 99)x≡2(mod 98)x≡51(mod 97)x≡10(mod 95)
这样的方式,可以加快计算速度,只有需要原来的值时,才需要进行100之外的计算。

费马小定理


如 果 p 为 素 数 , 且 a ∈ N , a 不 能 被 p 整 除 , 则 a p − 1 ≡ 1 ( m o d   p ) , 并 且 a p ≡ a ( m o d   p ) 如果p为素数,且a \in N,a不能被p整除,则\\ {a}^{p-1} \equiv 1 (mod\ p),并且 \\ a^p \equiv a (mod\ p) 如果p为素数,且a∈N,a不能被p整除,则ap−1≡1(mod p),并且ap≡a(mod p)

证明:

二项式展示公式
a p = ( 1 + ( a − 1 ) ) p = ∑ k = 0 p C p k 1 ( p − k ) ( a − 1 ) k , C p k = p ! ( p − k ) ! k ! = p ⋅ ( p − 1 ) ⋯ ( p − k + 1 ) k ! 其 中 因 为 C p k ∈ N , 所 以 k ! ∣ ( p ⋅ ( p − 1 ) ⋯ ( p − k + 1 ) ) , 同 时 因 为 0 < k < p , 所 以 g c d ( k ! , p ) = 1 , 即 k ! ∣ ( p − 1 ) ⋯ ( p − k + 1 ) , 即 p ∣ C p k , 然 后 我 们 将 上 面 二 项 式 展 开 公 式 进 行 m o d 2 的 处 理 , 化 简 为 : a p m o d    p = ( ∑ k = 0 p C p k 1 ( p − k ) ) m o d    p a p m o d    p ≡ 1 + ( a − 1 ) ) p ( m o d   m ) 上 面 我 们 将 a p 拆 分 成 ( 1 + ( a − 1 ) ) p , 那 么 是 不 是 同 样 可 以 拆 分 成 ( 2 + ( a − 2 ) ) p ( 3 + ( a − 3 ) ) p ⋮ ( a + ( a − a ) ) p 最 终 递 归 得 出 a p ≡ a ( m o d   p ) a^p=(1+(a-1))^p= \\ \sum^{p}_{k=0} {C}^{k}_{p} {1}^{(p-k)} {(a-1)}^{k},{C}^{k}_{p}=\frac{p!}{(p-k)!k!}=\frac{p \cdot (p-1) \cdots (p-k+1)}{k!} \\ 其中因为 {C}^{k}_{p} \in N,所以 k!|(p \cdot (p-1) \cdots (p-k+1)),同时因为0<k<p,所以 gcd(k!,p)=1,即\\ k!|(p-1)\cdots (p-k+1),即\\ p|{C}^{k}_{p},然后我们将上面二项式展开公式进行 mod 2的处理,化简为:\\ a^p \mod p =(\sum^{p}_{k=0} {C}^{k}_{p} {1}^{(p-k)}) \mod p \\ a^p \mod p \equiv 1+(a-1))^p (mod\ m) \\ 上面我们将 a^p 拆分成 (1+(a-1))^p,那么是不是同样可以拆分成 \\ (2+(a-2))^p\\ (3+(a-3))^p\\ \vdots (a+(a-a))^p\\ 最终递归得出 \\ a^p \equiv a (mod\ p) ap=(1+(a−1))p=k=0∑p​Cpk​1(p−k)(a−1)k,Cpk​=(p−k)!k!p!​=k!p⋅(p−1)⋯(p−k+1)​其中因为Cpk​∈N,所以k!∣(p⋅(p−1)⋯(p−k+1)),同时因为0<k<p,所以gcd(k!,p)=1,即k!∣(p−1)⋯(p−k+1),即p∣Cpk​,然后我们将上面二项式展开公式进行mod2的处理,化简为:apmodp=(k=0∑p​Cpk​1(p−k))modpapmodp≡1+(a−1))p(mod m)上面我们将ap拆分成(1+(a−1))p,那么是不是同样可以拆分成(2+(a−2))p(3+(a−3))p⋮(a+(a−a))p最终递归得出ap≡a(mod p)
参考B站视频

伪素数

简单来说就是,以前的中国人认为
如 果 n 为 奇 数 , 且 满 足 下 面 的 公 式 时 2 n − 1 ≡ 1 ( m o d   n ) , n 即 为 素 数 。 如果n为奇数,且满足下面的公式时 {2}^{n-1} \equiv 1 (mod\ n),n即为素数。 如果n为奇数,且满足下面的公式时2n−1≡1(mod n),n即为素数。
但是这个结论是错误的,而能推翻上面的数,就称为伪素数。比如
2 341 − 1 ≡ 1 ( m o d   341 ) 但 是 341 = 11 ⋅ 31 , 其 并 不 是 素 数 {2}^{341-1} \equiv 1 (mod\ 341) \\ 但是 341=11 \cdot 31,其并不是素数 2341−1≡1(mod 341)但是341=11⋅31,其并不是素数

卡米切尔数

首 先 是 一 个 正 整 数 n , 然 后 是 所 有 与 n 互 质 的 数 b , 都 满 足 b n − 1 ≡ 1 ( m o d   n ) 则 这 样 的 n 就 称 为 卡 米 切 尔 数 首先是一个正整数n,然后是所有与n互质的数b,都满足\\ {b}^{n-1} \equiv 1 (mod\ n) \\ 则这样的n就称为卡米切尔数 首先是一个正整数n,然后是所有与n互质的数b,都满足bn−1≡1(mod n)则这样的n就称为卡米切尔数

原根和离散对数

原根
设 定 两 个 数 , x 和 y , x , y ∈ Z , x 为 素 数 , 如 果 对 于 从 0 开 始 , 到 x − 1 中 的 每 一 个 正 整 数 , 假 设 为 k , 都 有 x k m o d   y = k 0 , 其 中 所 有 k 0 的 值 正 好 满 足 1 到 y − 1 时 , 则 称 x 是 y 的 原 根 设定两个数,x和y,x,y \in Z,x为素数,如果对于从0开始,到x-1中的每一个正整数,假设为k,都有 \\ {x}^{k} mod\ y={k}_{0},其中所有{k}_{0}的值正好满足 1到y-1时,则称x是y的原根 设定两个数,x和y,x,y∈Z,x为素数,如果对于从0开始,到x−1中的每一个正整数,假设为k,都有xkmod y=k0​,其中所有k0​的值正好满足1到y−1时,则称x是y的原根
例如x为2,y是11:
2 1 m o d    11 = 2 2 2 m o d    11 = 4 2 3 m o d    11 = 8 2 4 m o d    11 = 5 2 5 m o d    11 = 10 2 6 m o d    11 = 9 2 7 m o d    11 = 7 2 8 m o d    11 = 3 2 9 m o d    11 = 6 2 10 m o d    11 = 1 满 足 1 到 10 , 所 以 2 是 11 的 原 根 2^1 \mod 11=2 \\ 2^2 \mod 11=4 \\ 2^3 \mod 11=8 \\ 2^4 \mod 11=5 \\ 2^5 \mod 11=10 \\ 2^6 \mod 11=9 \\ 2^7 \mod 11=7 \\ 2^8 \mod 11=3 \\ 2^9 \mod 11=6 \\ {2}^{10} \mod 11=1 \\ 满足 1 到 10,所以2是11的原根 21mod11=222mod11=423mod11=824mod11=525mod11=1026mod11=927mod11=728mod11=329mod11=6210mod11=1满足1到10,所以2是11的原根
离散对数
在 上 面 原 根 的 基 础 上 , 假 设 a 是 介 于 0 到 y − 1 之 间 的 一 个 整 数 , 则 存 在 一 个 整 数 e , 使 得 x e m o d    y = a , 此 时 , 我 们 称 e 为 以 x 为 底 , a 模 y 的 离 散 对 数 , 写 作 l o g x a = e 在上面原根的基础上,假设 a 是介于0到y-1之间的一个整数,则存在一个整数e,使得 \\ {x}^{e} \mod y =a,此时,我们称e为以x为底,a模y的离散对数,写作 \\ {log}_{x} a =e 在上面原根的基础上,假设a是介于0到y−1之间的一个整数,则存在一个整数e,使得xemody=a,此时,我们称e为以x为底,a模y的离散对数,写作logx​a=e
注意:在上面的表示法中,没有展示y的值。

上一篇:微积分(A)随缘一题[8]


下一篇:函数与数列求和