剩余
剩余
前置知识:离散对数
模运算下的剩余问题,是将开方运算引入模运算的尝试。
定义
令整数 𝑘 ≥2
,整数 𝑎
,𝑚
满足 (𝑎,𝑚) =1
,若存在整数 𝑥
使得
𝑥𝑘≡𝑎(mod𝑚)(1)
则称 𝑎
为模 𝑚
的 𝑘
次剩余,否则称 𝑎
为模 𝑚
的 𝑘
次非剩余。
二次剩余 即是 𝑘
次剩余的特例。
性质
当整数 𝑘 ≥2
,整数 𝑎
,𝑚
满足 (𝑎,𝑚) =1
,模 𝑚
有原根 𝑔
时,令 𝑑 =(𝑘,𝜑(𝑚))
,则:
𝑎
为模 𝑚
的 𝑘
次剩余当且仅当 𝑑 ∣ind𝑔𝑎
,即:
𝑎𝜑(𝑚)𝑑≡1(mod𝑚)
方程 (1)
若有解,则模 𝑚
下恰有 𝑑
个解
模 𝑚
的 𝑘
次剩余类的个数为 𝜑(𝑚)𝑑
, 其有形式
𝑎≡𝑔𝑑𝑖(mod𝑚),(0≤𝑖<𝜑(𝑚)𝑑)
证明
令 𝑥 =𝑔𝑦
,则方程 (1)
等价于
𝑔𝑘𝑦≡𝑔ind𝑔𝑎(mod𝑚)
其等价于
𝑘𝑦≡ind𝑔𝑎(mod𝜑(𝑚))(2)
由同余的性质,我们知道 𝑦
有整数解当且仅当 𝑑 =(𝑘,𝜑(𝑚)) ∣ind𝑔𝑎
,进而
𝑎𝜑(𝑚)𝑑≡1(mod𝑚)⟺𝑔𝜑(𝑚)𝑑ind𝑔𝑎≡1(mod𝑚)⟺𝜑(𝑚)∣𝜑(𝑚)𝑑ind𝑔𝑎⟺𝜑(𝑚)𝑑∣𝜑(𝑚)ind𝑔𝑎⟺𝑑∣ind𝑔𝑎
当 𝑑 ∣ind𝑔𝑎
时,由同余的性质可知方程 (2)
模 𝜑(𝑚)
下恰有 𝑑
个解,进而方程 (1)
模 𝑚
下恰有 𝑑
个解。
由 1 知 𝑎
为模 𝑚
的 𝑘
次剩余当且仅当 𝑑 ∣ind𝑔𝑎
,故
ind𝑔𝑎≡𝑑𝑖(mod𝜑(𝑚)),(0≤𝑖<𝜑(𝑚)𝑑)
故模 𝑚
的 𝑘
次剩余共有 𝜑(𝑚)𝑑
个同余类:
𝑎≡𝑔𝑑𝑖(mod𝑚),(0≤𝑖<𝜑(𝑚)𝑑)
参考资料
- 冯克勤。初等数论及其应用。
本页面最近更新:2023/7/23 22:10:54,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:Great-designer, Tiphereth-A, ChungZH, iamtwz, Xeonacid
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用