剩余与单位根

剩余

模运算下的剩余问题，是将开方运算引入模运算的尝试。在复数中引入开方运算借助了多值的对数函数，在剩余问题中也可以借助离散对数来方便理解与讨论。

定义

一个数 \(a\)，如果与 \(n\) 互素，且模 \(n\) 同余于某个数的 \(k\) 次方，则称 \(a\) 为模 \(n\) 的 \(k\) 次剩余（residue）。一个不与 \(n\) 互素的数 \(b\)，不同余于任何数的 \(k\) 次方，则称 \(b\) 为模 \(p\) 的模 \(n\) 的 \(k\) 次非剩余。

解释

对 \(k\) 次剩余求解，也就是对常数 \(a\) 解下面的这个方程：

\[ x^k\equiv a\pmod n \]

通俗一些，可以认为是求模意义下的开 \(k\) 次方运算。

当模 \(n\) 存在原根 \(g\) 的时候，两边取对数：

\[ k\log_g x\equiv\log_g a\pmod{\varphi(n)} \]

从而转化为一个模 \(\varphi(n)\) 意义下的线性不定方程问题。

单位根

定义

考虑方程：

\[ x^k\equiv 1\pmod n \]

根据拉格朗日定理，这样的解最多有 \(k\) 个。称全部解为模 \(n\) 意义下的 \(k\) 次单位根（the \(k\)-th root of unity）。

解释

当模 \(n\) 存在原根 \(g\) 的时候，两边取对数：

\[ k\log_g x\equiv 0\pmod{\varphi(n)} \]

同样转化为一个模 \(\varphi(n)\) 意义下的线性不定方程问题。这个方程始终有解 \(1\)，并且也可以构造其他形式的解。可以设：

\[ \omega_k\equiv g^{\frac{\varphi(n)}{\gcd(k,\varphi(n))}}\pmod n \]

那么，模 \(n\) 意义下的全体 \(k\) 次单位根可以表示为：

\[ \{\omega_k^t\mid t=0,1\cdots,\gcd(k,\varphi(n))-1\} \]

选定原根 \(g\) 之后，如果不加说明，一般叙述的 \(k\) 次单位根即为上述 \(\omega_k\)，其它解均可以用 \(\omega_k\) 的幂表示。

单位根的个数就是上述集合的元素个数。与复数中的单位根不同，由于取值是离散而有限的，单位根的个数最多为 \(n\) 个，不随 \(k\) 的增加而无限增加。根据全体 \(k\) 次单位根的表达式写法，可以得到全体 \(k\) 次单位根的个数为：

\[ \gcd(k,\varphi(n)) \]

可见，如果 \(k\) 与 \(\varphi(n)\) 互素，则只有 \(1\) 是单位根。单位根的个数必然为 \(n\) 的约数，并且全体 \(\varphi(n)\) 个数均为 \(\varphi(n)\) 次单位根。

性质

单位根有三个重要的性质。对于任意正整数 \(k\) 和整数 \(t\)：

\[ \begin{aligned} \omega_k^k&\equiv 1\pmod n\\ \omega_k^t&\equiv \omega_{2k}^{2t}\pmod n\\ \omega_{2k}^{t+k}&\equiv -\omega_{2k}^t\pmod n\\ \end{aligned} \]

推导留给读者自证。这三个性质在快速数论变换中会得到应用。但要注意，后两条仅当 \(\omega_k\) 与 \(\omega_{2k}\) 不相等，即 \(2k\) 次单位根个数比 \(k\) 次单位根个数多时才成立。

本原单位根

模 \(n\) 意义下的 \(k\) 次单位根特指 \(\omega_k\)，是为了在应用时方便。

在解方程的视角看来，满足 \(\omega_k\) 性质的不止 \(\omega_k\) 一个，对于 \(\omega_k\) 的若干次幂也会满足类似的性质。

虽然这里的本原单位根与复数中的本原单位根表达的含义一致，性质的应用一致，但是由于这里的本原单位根取值离散而有限，并且每个数都是 \(\varphi(n)\) 次单位根，这里本原单位根的定义方法与复数中的本原单位根定义方法不同。

这种定义方法与阶的概念完全一致：

定义

一个数 \(a\) 模 \(n\) 的阶是 \(k\)，等价于 \(a\) 是模 \(n\) 的 \(k\) 次本原单位根。

如果一个数 \(a\) 是 \(k\) 次单位根，并且对于任意大于 \(0\) 小于 \(k\) 的 \(t\)，\(a\) 不是 \(t\) 次单位根，则 \(a\) 是 \(k\) 次本原单位根。

解释

由于阶的定义是唯一的，一个数 \(a\) 只有一个固定的阶，不同次数的本原单位根集合交集为空。

与复数中的本原单位根一致，如果存在 \(k\) 次本原单位根，借助任意一个 \(k\) 次本原单位根，都可以生成全体 \(k\) 次单位根。此时，全体 \(k\) 次单位根恰好为，对于全体 \(k\) 的约数 \(d\)，全体 \(d\) 次本原单位根集合的并集。

由于所有的数均为 \(\varphi(n)\) 次单位根，因此当 \(k\) 比 \(\varphi(n)\) 大的时候，不存在 \(k\) 次本原单位根。当且仅当 \(k\) 整除 \(\varphi(n)\) 的时候，存在 \(k\) 次本原单位根。

当 \(k\) 次本原单位根存在时，全体 \(k\) 次本原单位根的个数为 \(\varphi(k)\)。此时全体 \(k\) 次本原单位根恰好为：

\[ \{\omega_k^t\mid 0\le t<k, \gcd(k,t)=1\} \]

与复数中的本原单位根一致。

对于一般的 \(k\)，需要将 \(k\) 替换为 \(\gcd(n,k)\)。由于 \(\gcd(n,k)\) 是 \(n\) 的约数，进行替换之后则将问题转化为已讨论的情形。

剩余方程的解

借助单位根的概念可以很好地研究当原根 \(g\) 存在时，剩余方程

\[ x^k\equiv a\pmod n \]

的全体解，即与它等价的取对数之后的方程

\[ k\log_g x\equiv\log_g a\pmod{\varphi(n)} \]

的全体解。

当剩余方程存在一个解 \(x\) 的时候，方程的全体解恰好为 \(x\) 乘上全体 \(k\) 次单位根，因此个数恰好为单位根的个数 \(\gcd(k,\varphi(n))\)。因此，只要 \(a\) 是 \(k\) 次剩余，方程的解数即为 \(\gcd(k,\varphi(n))\)。

问题转化为剩余方程有解或无解的条件。根据裴蜀定理，当且仅当 \(\gcd(k,\varphi(n))\) 整除 \(\log_g a\) 时，方程有解，其余情形方程无解。

因此，全体 \(k\) 次剩余共有 \(\frac{\varphi(n))}{\gcd(k,\varphi(n))}\) 个，分别为

\[ \{{(g^{\gcd(k,\varphi(n))})}^t\mid t=0,1\cdots,\frac{\varphi(n))}{\gcd(k,\varphi(n))}-1\} \]

于是 \(k\) 次剩余和 \(k\) 次单位根恰好构成了互补的概念：

一个数 \(a\) 是 \(k\) 次剩余，等价于 \(a\) 是 \(\gcd(k,\varphi(n))\) 次剩余，等价于 \(a\) 是 \(\frac{\varphi(n))}{\gcd(k,\varphi(n))}\) 次单位根。

一个数 \(a\) 是 \(k\) 次单位根，等价于 \(a\) 是 \(\gcd(k,\varphi(n))\) 次单位根，等价于 \(a\) 是 \(\frac{\varphi(n))}{\gcd(k,\varphi(n))}\) 次剩余。

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用