Chap5 指数与原根

整数的次数

定义：设\(m > 0\)，\((a,m) = 1\)，\(l\) 是使 \[ a^l \equiv 1 \;(mod \,m) \] 成立的最小正整数，则 \(l\) 叫做 \(a\) 对模数 \(m\) 的次数

定理：设 \(a\) 对模数 \(m\) 的次数为 \(l\)， \(a^n \equiv 1 \;(mod\, m)\)，\(n > 0\)，则\(l \,|\, n\)

定理：设 \(a\) 对模数 \(m\) 的次数为 \(l\)，则 \[ 1,a,a^2,...,a^{l - 1} \] 对模数 \(m\) 两两不同余

定理：设 \(a\) 对模数 \(m\) 的次数为 \(l\)，\(\lambda > 0\)，\(a^\lambda\) 对模数 \(m\) 的次数为 \(l_1\)，则\(l_1 = \frac{l}{(l,\lambda)}\)

推论：设 \(a\) 对模数 \(m\) 的次数为 \(l\)，则 \(\phi(l)\) 个数 \[ a^\lambda,(\lambda,l) = 1, 0 < \lambda \leq l \] 对模数 \(m\) 的次数均为 \(l\)

定理：设 \(p\) 是一个素数，如果存在整数 \(a\) ，它对模数 \(p\) 的次数是 \(l\)，则恰有 \(\phi(l)\) 个对模数 \(p\) 两两不同余的整数，它们对模数 \(p\) 的次数都为 \(l\)

定理：设 \(l\,|\,p - 1\)，则次数是 \(l\) 的，模数 \(p\) 互不同余的整数个数是 \(\phi(l)\) 个

原根

定义：设整数 \(m > 0\) ，\((g,m) = 1\)，如果整数 \(g\) 对 \(m\) 的次数为 \(\phi(m)\) ，则 \(g\) 叫做 \(m\) 的一个原根

定理：设 \((g,m) = 1\)，\(m > 0\)，则 \(g\) 是 \(m\) 的一个原根的充要条件是 \[ g,g^2,...,g^{\phi(m)} \] 组成模数 \(m\) 的一组缩系

原根的重要意义：原根的存在使得一个模数 \(m\) 的一组缩系课表示成一组几何级数

定理：设 \(m > 1\)，若 \(m\) 有原根，则 \(m\) 必为下列诸数之一：2，4，\(p^l\)，\(2p^l\)，这里 \(l \geq 1\)，\(p\) 是奇素数

定理：\(m = 2,4,p^l,2p^l\)(\(l \geq 1\)，\(p\) 为奇素数)时，\(m\) 有原根

定理：设 \(m\) 有一个原根 \(g\)，则 \(m\) 恰有 \(\phi(\phi(m))\) 个对模数 \(m\) 不同余的原根，它们由集 \[ S = \{g^t\,|1 \leq t \leq \phi(m)，(t,\phi(m)) = 1\} \] 中的数给出

计算次数的方法

定理：如果 \(m = p_1^{l_1}p_2^{l_2}...p_k^{l_k}\) 是 \(m\) 的标准分解式，整数 \(a\) 对模数 \(m\) 的次数等于整数 \(a\) 对模数 \(p_i^{l_i}\) 的诸次数的最小公倍数

定理： 设 \(p\) 是一个素数，\(a\) 对模数 \(p^j\) 的次数是 \(f_j\)，则 \(f_{j + 1} = f_j\) 或 \(f_{j + 1} = pf_j\). 又设 \(p^i || a^{f_2} - 1\)，进而有 \[ f_j = \begin{cases}f_2,\;\;\;\;\;\;({if}\;\;\; 2 \leq j \leq i)\\p^{j - 1}f_2\;\;\;(if\;\;j > i)\end{cases} \]

计算原根的方法

定理：设 \(m > 2\)，\(\phi(m)\) 的所有不同的素因子是 \(q_1,q_2,...,q_s\)，\((g,m) = 1\)，则 \(g\) 是 \(m\) 的一个原根的充要条件是： \[ g^{\frac{\phi(m)}{q_i}} \not \equiv 1 \;\;(mod\;m) \]

定理：设 \(a\) 对模数奇素数 \(p\) 的次数是 \(d\)，\(d < p - 1\)，则 \[ a^\lambda,\;\;\; \lambda = 1,2,...,d \] 都不是 \(p\) 的原根

指数

定义：任一整数 \(n\)，\((n,m) = 1\)，必有唯一的整数 \(k\)，\(0 \leq k < \phi(m)\)，满足 \[ n ≡ g^k \;\;(mod\, m) \] \(k\) 叫做 \(n\) 对模数 \(m\) 的指数，记为 \(k = ind_g n\)，在不易引起混淆的情况下，把 \(ind_g n\)简写成 \(ind \,n\). 有时也把指数叫做离散对数

指数具有类似对数的性质，我们有如下定理 定理：设 \(g\) 是 \(m\) 的原根，如果 \((a,m) = (b,m) = 1\)，我们有： 1. \(ind(ab) ≡ ind\,a + ind\,b\;(mod\,m) = 1\) 2. \(ind\,a^n ≡ nind\,a\;(mod\, m)\) 3. \(ind\,1 = 0,\,ind\,g = 1\) 4. \(ind(-1) = \frac{\phi(m)}{2}\;(m > 2)\) 5. 设 \(g_1\) 也是 \(m\) 的一个原根，则 \[ ind_ga ≡ ind_{g_1}a \cdot ind_{g}g_1\;(mod\, \phi(m)) \]

定义：设 \(k > 0\)，\(m > 0\)，一个形如 \[ x^k ≡ n\;(mod\, m) \] 的同余式，叫做二项同余式

定理：设 \(m\) 有原根 \(g\)，\((n,m) = 1\)，二项同余式 \[ x^k ≡ n\;(mod\, m) \] 有解的充要条件是 \(d = (k,\phi(m)) | ind_gn\). 如果此同余式有解，则恰有 \(d\) 个解