跳转至

剩余与单位根

剩余

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

定义

一个数 \(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))}\) 次剩余。