原根与模算术

摘要

啃课件的时侯遇到的数论题,于是来填坑

阶与原根

如果 (a,m)=1,记 x 为最小的正整数使得 . 那么 x 称为 的阶。记为

可以把阶理解为模意义下 1 的最小次方根。

如果 的阶是 ,那么 的原根

即原根为模意义下 1 的 次方根,且保证没有更小的次方。

相关定理结论

根据欧拉定理, 。因此

当且仅当

有原根的充要条件是 ,其中 是奇素数, 是任意正整数

有原根时,它有 个原根

素数的原根

结论:每个素数都有原根。

如果 p 是一个奇素数且有原根 r,那么 r 或者 r+p 是模 的一个原根。

对于任意正整数 k, 都存在原根。如果 r 是模 的原根,那么它也是模 的原根。

离散对数和指数

在模 m 意义下(m 有原根 r)

使得 的唯一整数 x 称为 a 模 m 以 r 为底的指数,记为 。这里不标明 m 是因为我们假定在计算过程中,m 恒定不变。

其实相当于把 改写成 而已。不同的是,这个底数只能取原根。

离散对数和对数的性质很相似。设 a,b 与 m 互质,在模 意义下:

  1. .
  2. .
  3. .

同余方程与离散对数

根据相关定理结论的第二条,同余方程与离散对数方程是可以转换的。一般地说,对于同余方程 ,m 有原根 r 时,可以先取离散对数,转化为 求解。求解了 的所有值后再计算指数 即可得到所有 x 的解。

求同余方程 的解

先转化为离散对数。已知 3 是 17 的一个原根,对数表如下

a a a a
1 16 5 5 9 2 13 4
2 14 6 15 10 3 14 9
3 1 7 11 11 7 15 6
4 12 8 10 12 13 16 8

方程转化为

可得 .

,即 .


  转载请注明: Sshwy's Blog 原根与模算术

 上一篇
[NOIP2012] 开车旅行 [NOIP2012] 开车旅行
摘要 倍增优化 DP 小 A 和小 B 决定旅行,城市从 1 到 N 编号,编号较小的城市在编号较大的城市的西边,各个城市的海拔高度互不相同,记城市 i 的海拔高度为 ,城市 i 和城市 j 之间的距离 $d[i,j]=|H_
2019.06.13
下一篇 
[BZOJ2219] 数论之神 [BZOJ2219] 数论之神
摘要 啃课件的时侯遇到的,先放个题解,至于代码的话先咕着 多组数据( 1. . X 在范围 [0, 2K] 内 的 X 的个数. 即求同余方程 $x^a\equiv b\b
2019.06.08
  目录