剩餘
剩餘
前置知識：離散對數
模運算下的剩餘問題，是將開方運算引入模運算的嘗試。
定義
令整數 \(k\geq 2\)，整數 \(a\)，\(m\) 滿足 \((a,m)=1\)，若存在整數 \(x\) 使得
則稱 \(a\) 為模 \(m\) 的 \(k\) 次剩餘，否則稱 \(a\) 為模 \(m\) 的 \(k\) 次非剩餘。
二次剩餘 即是 \(k\) 次剩餘的特例。
性質
當整數 \(k\geq 2\)，整數 \(a\)，\(m\) 滿足 \((a,m)=1\)，模 \(m\) 有原根 \(g\) 時，令 \(d=(k,\varphi(m))\)，則：
-
\(a\) 為模 \(m\) 的 \(k\) 次剩餘當且僅當 \(d\mid \operatorname{ind}_g a\)，即：
\[ a^{\frac{\varphi(m)}{d}}\equiv 1\pmod m \] -
方程 \((1)\) 若有解，則模 \(m\) 下恰有 \(d\) 個解
-
模 \(m\) 的 \(k\) 次剩餘類的個數為 \(\dfrac{\varphi(m)}{d}\), 其有形式
\[ a\equiv g^{di}\pmod m,\qquad \left(0\leq i<\frac{\varphi(m)}{d}\right) \]
證明
-
令 \(x=g^y\)，則方程 \((1)\) 等價於
\[ g^{ky}\equiv g^{\operatorname{ind}_g a}\pmod m \]其等價於
\[ ky\equiv \operatorname{ind}_g a\pmod{\varphi(m)}\tag{2} \]由同餘的性質，我們知道 \(y\) 有整數解當且僅當 \(d=(k,\varphi(m))\mid \operatorname{ind}_g a\)，進而
\[ \begin{aligned} a^{\frac{\varphi(m)}{d}}\equiv 1\pmod m&\iff g^{\frac{\varphi(m)}{d}\operatorname{ind}_g a}\equiv 1\pmod m\\ &\iff \varphi(m)\mid\frac{\varphi(m)}{d}\operatorname{ind}_g a\\ &\iff \varphi(m)d\mid \varphi(m)\operatorname{ind}_g a\\ &\iff d\mid \operatorname{ind}_g a\\ \end{aligned} \] -
當 \(d\mid \operatorname{ind}_g a\) 時，由同餘的性質可知方程 \((2)\) 模 \(\varphi(m)\) 下恰有 \(d\) 個解，進而方程 \((1)\) 模 \(m\) 下恰有 \(d\) 個解。
-
由 1 知 \(a\) 為模 \(m\) 的 \(k\) 次剩餘當且僅當 \(d\mid \operatorname{ind}_g a\)，故
\[ \operatorname{ind}_g a\equiv di\pmod{\varphi(m)},\qquad \left(0\leq i<\frac{\varphi(m)}{d}\right) \]故模 \(m\) 的 \(k\) 次剩餘共有 \(\dfrac{\varphi(m)}{d}\) 個同餘類：
\[ a\equiv g^{di}\pmod m,\qquad \left(0\leq i<\frac{\varphi(m)}{d}\right) \]
參考資料
- 馮克勤。初等數論及其應用。
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用