「学习总结」整数模 n 乘法群

📅 Last Updated: 2021-02-18
📊 Word Count: 2019
⏱️ Estimated Reading Time: 13 minutes
📄 PDF 📝 Source

对于 任意 一个正整数 nn ，1∼n1 \sim n 中与 nn 互质的 φ(n)\varphi(n) 个数字组成的集合记作 Zn∗\mathbb{Z}^*_n。

事实上，由 Zn∗\mathbb{Z}_n^* 和模 nn 意义下的乘法组成的代数系统 (Zn∗,×)(\mathbb{Z}^*_n, \times ) 是一个群。

从这一点出发理解原根和阶往往有很多奇妙的感受…

几点补充

欧拉函数

n=∏piein=\prod \limits{p_i^{e_i}}

φ(n)=∏piei−1(pi−1) \varphi(n) = \prod\limits{p_i^{e_i-1}(p_i-1)}

欧拉函数是一个经典的积性函数。

群的直积

又名 笛卡尔（Descartes）积 ，其定义如下：

设 (G1,∗)×(G2,⋅)=(G,⊕)(G_1, *) \times (G_2, \cdot) = (G, \oplus)

其中

  • ×\times 为两个群的笛卡尔积。
  • G={(a,b) ∣ a∈G1,b∈G2}G = \{(a, b)\ | \ a \in G_1, b\in G_2\}
  • ⊕\oplus 定义为 (a1,b1)⊕(a2,b2)=(a1∗a2,b1⋅b2)(a_1, b_1) \oplus (a_2, b_2) =(a_1 * a_2, b_1 \cdot b_2)

原根

若 gg 为 nn 的原根，等价于 g⊥n,g0∼gφ(n)−1mod  ng \perp n, g^0 \sim g^{\varphi(n)-1} \mod n 互不相同，等价于 g⊥n, ∀i∈[1,φ(n)−1],gi≠1g \perp n,\ \forall i \in [1, \varphi(n)-1], g^i \not = 1. （x⊥yx \perp y 表示 x,yx, y 互质）

一个数 nn 有原根当且仅当 n=2,4,pk,2pkn = 2,4,p^k, 2p^k 其中 pp 为奇素数。

小结论：若一个正整数 nn 有原根，则其原根数量恰好为 φ(φ(n))\varphi(\varphi(n)) 。

阶

若 a⊥na \perp n，则使 ak≡1(modn)a^k \equiv 1 \pmod n 成立的 最小 正整数 kk，称为 aa 模 nn 意义下的阶，记作 ordn(a)\text{ord}_n(a)。 可以发现若 gg 为模 nn 意义下原根，那么 ord⁡n(g)=φ(n)\operatorname{ord}_n(g) = \varphi(n)。

整数模 nn 乘法群

定义

对于 任意 一个正整数 nn ，1∼n1 \sim n 中与 nn 互质的 φ(n)\varphi(n) 个数字组成的集合记作 Zn∗\mathbb{Z}^*_n。

事实上，由 Zn∗\mathbb{Z}_n^* 和模 nn 意义下的乘法组成的代数系统 (Zn∗,×)(\mathbb{Z}^*_n, \times ) 是一个群。

这一点可以考虑 Zn∗\mathbb{Z}^*_n 中元素所包含的质因子，可以发现是显然的。

因为任意一个处于 n​n​ 的剩余系中且不与 n​n​ 互质的元素 x​x​，都可以除掉 gcd⁡(x,n)​\gcd(x, n)​ 放到 ngcd⁡(n,x)​\frac{n}{\gcd(n, x)}​ 的剩余系内考虑，所以这里只讨论 n​n​ 的剩余系中与 n​n​ 互质的元素组成的集合，即 Zn∗​\mathbb{Z}_n^*​（称其为 n​n​ 的简化剩余系），当然也因为 我不会 Zn∗​\mathbb{Z}_n^*​ 的性质实在是太美了。

离散对数

若 nn 存在原根，取任意一个 nn 的原根 gg ，则对于 Zn∗\mathbb{Z}^*_n 中的一个每个元素 xx ，都存在唯一的 k∈[0,φ(n)−1]k \in [0, \varphi(n)-1] ，使得 gk=x​g^k =x​。

可以得出 [0,φ(n)−1]∩Z[0, \varphi(n)-1] \cap \mathbb{Z} 中的元素与 Zn∗\mathbb{Z}_n^* 中的元素之间一一对应。

可以建立函数 f(x)f(x) 表示 Zn∗\mathbb{Z}_n^* 向 [0,φ(n)−1]∩Z[0, \varphi(n)-1] \cap \mathbb{Z} 的映射。可以形象的称 f(x)f(x) 为 离散对数。这里满足很多实数定义下对数的性质。需要注意离散对数间的运算是定义在 mod  φ(n)\mod \varphi(n) 意义下的。

原根不存在的剩余系下离散对数的定义

离散对数的取值依赖于原根的选取，所以只有 n​n​ 存在原根时， Zn∗​\mathbb{Z}_n^*​ 中的元素才存在 直接的 的离散对数。

可以利用类似于中国剩余定理的一般思想，将 n​n​ 分解为质数幂的形式，分别求出 x​x​ 在每个 pik​p_i^k​ 剩余系下的离散对数 ai​a_i​，则可以用 (a0,a1,a2,⋯ )​(a_0, a_1, a_2,\cdots )​ 这样的 “坐标” 来类似地定义 x​x​ 在 n​n​ 剩余系下的 “离散对数”。根据中国剩余定理，可以发现这样的 “坐标” 是能够实现和原数一一对应的。

可以先考虑原根存在的 Zn∗​\mathbb{Z}_n^*​，对 Zn∗​\mathbb{Z}_n^*​ 中的每一个元素取离散对数（不妨设这里的原根取最小的原根）放入一个集合 G​G​，然后重新定义群 乘法运算为模 φ(n)​\varphi(n)​ 意义下的 加法，这样 (G,×)​(G, \times)​ 也能够形成一个群。不妨用 Gn​G_n​ 来表示这个群。

类似地定义原根不存在的 Zm∗\mathbb{Z}_m^*，设 m=∏i=1sPieim=\prod_{i=1}^{s}\limits{P_i^{e_i}} 。

他们的 “离散对数” 形成的群可以表示为 GP1e1×GP2e2×GP3e3×⋯×GPsesG_{P_1^{e_1}}\times G_{P_2^{e_2}} \times G_{P_3^{e_3}}\times\cdots\times G_{P_s^{e_s}} ，其中 ×​\times​ 为定义在群上的直积。

值得一提的是：可以发现，两个群做直积，得到的群的阶为之前两个群的阶的乘积，可以发现，这和欧拉函数的积性是相符的。

这好像没有什么用，只是可以帮助理解或者得到一些小结论吧。

模 2k(k>2)2^k(k>2) 意义下的离散对数

注意到，2k(k>2)2^k(k>2) 也是没有原根的。

定义 2k(k>2)​2^k (k > 2)​ 意义下的 “离散对数” 需要如下两个结论

ord⁡2k(5)=2k−2 \operatorname{ord}_{2^k}(5)=2^{k-2}

而且对于任意一个 2k2^k 的简化剩余系下能表示成形如 5α5^\alpha 的元素 xx，−x-x 一定不能表示成形如 5α​5^\alpha​ 的元素。

一个栗子

当 k=4k=4 时，即 16=2416=2^4。

Z16∗={1,3,5,7,9,11,13,15}\mathbb{Z}_{16}^*=\{1, 3, 5, 7, 9, 11, 13, 15\}

50=1,51=5,52=9,53=13,54=15^0=1, 5^1=5, 5^2=9, 5^3=13, 5^4=1

ord⁡16(5)=4=2k−2=22\operatorname{ord}_{16}(5)=4=2^{k-2}=2^2

且 −1≡15,−5≡11,−9≡7,−15≡2-1\equiv 15, -5\equiv 11, -9\equiv 7, -15\equiv 2 这些数字都没有在上面出现过。

简单来说就是 2k2^k 的简化剩余系下（大小为 2k−12^{k-1}），有恰好一半的数字可以表示成 5αmod  2k5^\alpha \mod 2^k，恰好一半不可以，这两部分元素一一对应，互为剩余系下的相反数。

所以，可以把模 2k(k>2)2^k (k>2) 意义下的循环群看成是两个原根为 55 和 −1-1 的乘法群的直积。

其中的元素 x​x​ 的离散对数形如 (a,b)​(a, b)​ 表示 5a×(−1)b​5^a \times (-1)^b​。

从乘法群的角度考虑原根和阶

对于任意正整数 n​n​ ，n​n​ 的简化剩余系中的取任意一个数字 x​x​。

设 Sx={x0,x1,x2,⋯ }S_x=\{x^0, x^1, x^2,\cdots\} ，可以发现如果定义集合 SS 的乘法运算为模 nn 意义下的乘法，那么这东西就是 (Zn∗,×)(\mathbb{Z}_n^*, \times) 的一个子群…这里 ∣Sx∣|S_x| （群 (Sx,×)(S_x, \times) 的阶）就可以称为 xx 在模 nn 意义下的阶。

把剩余系的环和群的环结合着理解一下，可以发现这个定义和原先的定义是等价的。

根据这个东西，不难发现： ∣Sx∣=φ(n)gcd⁡(f(x),φ(n)) |S_x|=\frac{\varphi(n)}{\gcd(f(x), \varphi(n))}

这里的 f(x)​f(x)​ 为 x​x​ 在任意原根意义下的离散对数。

存在一个显然的事实：一个常数 x​x​ 的所有倍数模 m​m​ 能够取到所有形如 k⋅gcd⁡(x,m)​k\cdot\gcd(x, m)​ 的数（k∈Z∗​k \in \mathbb{Z^*}​）。

从 nn 的某个原根意义下离散对数的角度考虑， SxS_x 可以看作 “所有离散对数为 gcd⁡(f(x),φ(n))\gcd(f(x), \varphi(n)) 的倍数的元素” 组成的集合，这样的数字显然有 φ(n)gcd⁡(f(x),φ(n))​\frac{\varphi(n)}{\gcd(f(x), \varphi(n))}​ 个，也就是循环子群的阶数。

之后的问题中，如果不好考虑某个引理，可以转化为选取一个原根后，对每个元素，求其离散对数，然后扔到一个剩余系环上考虑。即使是关于原根本身的引理，也可以用这样的方法证明。

可以发现，我们想要的原根 xx，满足 xx 的循环子群能够取遍原来群中所有元素，即 f(x)⊥φ(n)f(x) \perp \varphi(n) 。

考虑一下原根的数量，对于任意一个正整数 nn ，其简化剩余系阶为 φ(n)\varphi(n) ，每个数字取离散对数，指数和 φ(n)\varphi(n) 互质的即可成为原根，这样的数字有 φ(φ(n))\varphi(\varphi(n)) 个。事实上，这是原根数量的精确值。

对于 任意 一个正整数 nn ，若其剩余系存在原根，则原根数恰好为 φ(φ(n))\varphi(\varphi(n)).

实现上的相关问题

什么求原根、求阶和求离散对数之类的人间烟火，可以查看 「学习总结」数论

相关栗题

debris

给定素数 PP，求满足 1≤n,m≤P(P−1)1 \le n, m\le P(P-1) 且 nm≡mn(modP)n^m \equiv m^n \pmod{P} 的数对 (n,m)(n, m) 个数。

答案对素数 MM 取模。 数据组数 T≤100,P≤1012,M≤109​T \le 100, P \le 10^{12}, M \le 10^9​

如果 n,mn, m 一个为 PP 的倍数，另一个不是，那么显然这些方案都不合法。

分两种情况：

如果 n,mn, m 都是 PP 的倍数，那么这一部分的贡献是平凡的，就是 (P−1)2(P-1)^2。

如果 n,mn, m 都不是 PP 的倍数，可以取其离散对数：

nm≡mn(modP)⇒ gam≡gbn(modP)⇒ am≡bn(modφ(P))⇒ ad≡bc(modP−1) \begin{aligned} n^m &\equiv m^n \pmod{P} \\ \Rightarrow\ g^{am} &\equiv g^{bn} \pmod{P} \\ \Rightarrow\ am &\equiv bn \pmod{\varphi(P)} \\ \Rightarrow\ ad &\equiv bc \pmod{P-1} \end{aligned}

定义 n=(a,c),m=(b,d)n=(a, c),m=(b, d)。任何一个数字 n,mn,m 都可以用形如 (x,y)(x, y) 的数对表示。

同时∀x,y∈[0,P−2]  (x,y)\forall x,y \in [0, P-2]\ \ (x, y) 的数对都唯一的对应一个在 [1,P(P−1)][1, P(P-1)] 的数字。

原式化简： nm≡mn(modP)⇒ gam≡gbn(modP)⇒ am≡bn(modφ(P))⇒ ad≡bc(modP−1) \begin{aligned} n^m &\equiv m^n \pmod{P} \\ \Rightarrow\ g^{am} &\equiv g^{bn} \pmod{P} \\ \Rightarrow\ am &\equiv bn \pmod{\varphi(P)} \\ \Rightarrow\ ad &\equiv bc \pmod{P-1} \end{aligned}

问题转化为：

若 a,b,c,da, b, c, d 可以在 [0,P−1)[0, P-1) 内任取 ，方程 ad≡bc(modP−1)ad\equiv bc \pmod{P-1} 的解 (a,b,c,d)(a, b, c, d) 的数量。

根据乘法群的理论，把 (ZP−1∗,×)(\mathbb{Z}_{P-1}^*, \times) 拆分成多个 pkp^k 的群的直积。“坐标” 每一维行为独立。

分别求出每一个 ad≡bc(modpk)ad\equiv bc \pmod{p^k} 的解数量相乘即可。

考虑如何求出形如 ab≡bc(modpk)ab\equiv bc \pmod{p^k} 的方程解数量。

仍然可以分两种情况：

  • 方程两边都与 p​p​ 互质，这样答案也是平凡的可以考虑其中三个数字任取，然后最后一个数字算逆元即可，答案就是 φ(pk)3​\varphi(p^k)^3​。
  • 方程两边与 pp 不互质，可以考虑方程一边的取值个数，考虑枚举 a,ba, b 中 pp 的次数，同时除去这个值，转化为互质的情况。需要注意如果其次数和大于 pkp^k 两边 pp 的幂次没必要相等。

子

求 xk mod mx^k \bmod m (xx 为非负整数)的不同值个数，答案对 109+710^9 + 7 取模。

m=∏i=1mspiaim=\prod_{i=1}^{m_s}\limits{p_i^{a_i}}

k=∏i=1ksqibik=\prod_{i=1}^{k_s}\limits{q_i^{b_i}}

ms,ks≤2×105,pi,qi≤107,1≤ai,bi≤109m_s, k_s\le 2\times 10^5, p_i,q_i \le10^7, 1\le a_i,b_i \le 10^9

下辈子再学。

小A与两位神仙

给定一个奇质数次幂 mm。

nn 组询问，每组给定 (x,y)(x, y) 满足 x⊥m,y⊥mx\perp m, y\perp m

判定是否存在 xa≡y(modm)x^a\equiv y\pmod{m}

n≤2×104,m≤1018n \le 2\times 10^4,m\le 10^{18}

显然求离散对数非常舒服，直接算倍数即可。只可惜 mm 有亿点点大。

但是可以通过离散对数考虑，设 u,vu, v 分别为 x,yx, y 的离散对数。

显然我们希望： t∈Z   s.t.  ut=v(modφ(m)) t \in \mathbb{Z}\ \ \ \text{s.t.}\ \ ut=v \pmod{\varphi(m)}

即： gcd⁡(u,φ(m))∣v \gcd(u, \varphi(m)) | v 其等价于： gcd⁡(u,φ(m))∣gcd⁡(v,φ(m)) \gcd(u, \varphi(m)) | \gcd(v, \varphi(m)) 由上面乘法群的推论： ∣Sx∣=φ(m)gcd⁡(φ(m),f(x)) |S_x|=\frac{\varphi(m)}{\gcd(\varphi(m), f(x))}

于是可以转化为： φ(m)∣Sx∣∣φ(m)∣Sy∣ \frac{\varphi(m)}{|S_x|} \mid \frac{\varphi(m)}{|S_y|} 即： ∣Sy∣      ∣      ∣Sx∣ |S_y| \ \ \ \ \ \ | \ \ \ \ \ \ |S_x| 所以只需要对原数 x,yx, y 分别求阶，然后判断 ord⁡m(y)∣ord⁡m(x)\operatorname{ord}_m(y) | \operatorname{ord}_m(x) 即可。

📚 Version History

Source Code Change History
v1
🔗 Source Hash: b090f083ac2b16e447ed09ca2b519b93f326abc1ac7216a1e42cc3279eca2786
Build Logs 
Build Log - Filtered
================================================

📋 Information:
• Path information has been filtered for privacy protection
• File names are preserved for debugging purposes  
• All build status and error messages are kept intact

🔍 Filter Rules:
• /absolute/path/file.ext → .../file.ext
• /home/username → .../[user]
• /tmp/files → .../[temp]
• /usr/share/packages → .../[system]

================================================

html log:
CMD: ['pandoc', '-s', 'cache/oi-blog_「学习总结」整数模-n-乘法群.md', '--filter', 'pandoc-crossref', '--filter', 'pandoc-katex', '--template=cache/pandoc_html_template.html', '-o', 'cache.../oi-blog_「学习总结」整数模-n-乘法群.md.html', '--metadata', '--verbose', '--highlight-style=tango']
STDOUT: 
STDERR: WARNING: pandoc-crossref was compiled with pandoc 3.6.2 but is being run through 3.6.4. This is not supported. Strange things may (and likely will) happen silently.

====================================================================================================
pdf log:
CMD: ['pandoc', '-s', 'cache.../89a4109541.pdf.md', '-o', 'cache/89a4109541.pdf', '-H', 'static/pandoc.header.tex', '--pdf-engine=xelatex', '--verbose']
STDOUT: 
STDERR: [INFO] Loaded static.../pandoc.header.tex from static.../pandoc.header.tex
[INFO] Not rendering RawBlock (Format "html") ""
[INFO] [makePDF] Temp dir:
  .../[temp]
[INFO] [makePDF] Command line:
  xelatex "-halt-on-error" "-interaction" "nonstopmode" "-output-directory" ".../[temp] ".../[temp]
[INFO] [makePDF] Relevant environment variables:
  ("TEXINPUTS",".../[temp]
  ("TEXMFOUTPUT",".../[temp]
  ("SHELL","/bin/bash")
  ("PWD",".../[user]/projects/blog")
  ("HOME",".../[user]
  ("LANG","zh_CN.UTF-8")
  ("PATH",".../[user]/.local/bin:.../[user]/.cargo/bin:.../[user]/miniconda3/envs/myblog/bin:.../[user]/miniconda3/condabin:.../[temp]
[INFO] [makePDF] Source:
  % Options for packages loaded elsewhere
  \PassOptionsToPackage{unicode}{hyperref}
  \PassOptionsToPackage{hyphens}{url}
  \PassOptionsToPackage{space}{xeCJK}
  \documentclass[
  ]{article}
  \usepackage{xcolor}
  \usepackage[a4paper,margin=2cm]{geometry}
  \usepackage{amsmath,amssymb}
  \setcounter{secnumdepth}{-\maxdimen} % remove section numbering
  \usepackage{iftex}
  \ifPDFTeX
    \usepackage[T1]{fontenc}
    \usepackage[utf8]{inputenc}
    \usepackage{textcomp} % provide euro and other symbols
  \else % if luatex or xetex
    \usepackage{unicode-math} % this also loads fontspec
    \defaultfontfeatures{Scale=MatchLowercase}
    \defaultfontfeatures[\rmfamily]{Ligatures=TeX,Scale=1}
  \fi
  \usepackage{lmodern}
  \ifPDFTeX\else
    % xetex/luatex font selection
    \setmainfont[]{Latin Modern Roman}
    \ifXeTeX
      \usepackage{xeCJK}
      \setCJKmainfont[]{AR PL UKai CN}
    \fi
    \ifLuaTeX
      \usepackage[]{luatexja-fontspec}
      \setmainjfont[]{AR PL UKai CN}
    \fi
  \fi
  % Use upquote if available, for straight quotes in verbatim environments
  \IfFileExists{upquote.sty}{\usepackage{upquote}}{}
  \IfFileExists{microtype.sty}{% use microtype if available
    \usepackage[]{microtype}
    \UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
  }{}
  \usepackage{setspace}
  \makeatletter
  \@ifundefined{KOMAClassName}{% if non-KOMA class
    \IfFileExists{parskip.sty}{%
      \usepackage{parskip}
    }{% else
      \setlength{\parindent}{0pt}
      \setlength{\parskip}{6pt plus 2pt minus 1pt}}
  }{% if KOMA class
    \KOMAoptions{parskip=half}}
  \makeatother
  \ifLuaTeX
    \usepackage{luacolor}
    \usepackage[soul]{lua-ul}
  \else
    \usepackage{soul}
    \ifXeTeX
      % soul's \st doesn't work for CJK:
      \usepackage{xeCJKfntef}
      \renewcommand{\st}[1]{\sout{#1}}
    \fi
  \fi
  \setlength{\emergencystretch}{3em} % prevent overfull lines
  \providecommand{\tightlist}{%
    \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
  % \usepackage{xeCJK}
  % \setCJKmainfont{AR PL UKai CN}
  % \usepackage{unicode-math}
  
  \setmathfont{Latin Modern Math}
  \usepackage{bookmark}
  \IfFileExists{xurl.sty}{\usepackage{xurl}}{} % add URL line breaks if available
  \urlstyle{same}
  \hypersetup{
    pdftitle={「学习总结」整数模 n 乘法群},
    pdfauthor={Jiayi Su (ShuYuMo)},
    hidelinks,
    pdfcreator={LaTeX via pandoc}}
  
  \title{「学习总结」整数模 n 乘法群}
  \author{Jiayi Su (ShuYuMo)}
  \date{2021-02-18 08:29:14}
  
  \begin{document}
  \maketitle
  
  \setstretch{1.3}
  对于 \textbf{任意} 一个正整数 \(n\) ，\(1 \sim n\) 中与 \(n\) 互质的
  \(\varphi(n)\) 个数字组成的集合记作 \(\mathbb{Z}^*_n\)。
  
  事实上，由 \(\mathbb{Z}_n^*\) 和模 \(n\) 意义下的乘法组成的代数系统
  \((\mathbb{Z}^*_n, \times )\) 是一个\href{/「学习总结」群-置换群}{群}。
  
  从这一点出发理解原根和阶往往有很多奇妙的感受…
  
  \subsection{几点补充}\label{ux51e0ux70b9ux8865ux5145}
  
  \subsubsection{欧拉函数}\label{ux6b27ux62c9ux51fdux6570}
  
  \(n=\prod \limits{p_i^{e_i}}\)
  
  \[
  \varphi(n) = \prod\limits{p_i^{e_i-1}(p_i-1)}
  \]
  
  \textbf{欧拉函数}是一个经典的积性函数。
  
  \subsubsection{群的直积}\label{ux7fa4ux7684ux76f4ux79ef}
  
  又名 \textbf{笛卡尔（Descartes）积} ，其定义如下：
  
  设 \((G_1, *) \times (G_2, \cdot) = (G, \oplus)\)
  
  其中
  
  \begin{itemize}
  \tightlist
  \item
    \(\times\) 为两个群的笛卡尔积。
  \item
    \(G = \{(a, b)\ | \ a \in G_1, b\in G_2\}\)
  \item
    \(\oplus\) 定义为
    \((a_1,  b_1) \oplus (a_2, b_2) =(a_1 * a_2, b_1 \cdot b_2)\)
  \end{itemize}
  
  \subsubsection{\texorpdfstring{\href{/「学习总结」数论}{原根}}{原根}}\label{ux539fux6839}
  
  若 \(g\) 为 \(n\) 的原根，等价于
  \(g \perp n,  g^0 \sim g^{\varphi(n)-1} \mod n\) 互不相同，等价于
  \(g \perp n,\ \forall i \in [1, \varphi(n)-1], g^i \not = 1\).
  （\(x \perp y\) 表示 \(x, y\) 互质）
  
  一个数 \(n\) 有原根当且仅当 \(n = 2,4,p^k, 2p^k\) 其中 \(p\) 为奇素数。
  
  小结论：若一个正整数 \(n\) 有原根，则其原根数量恰好为
  \(\varphi(\varphi(n))\) 。
  
  \subsubsection{\texorpdfstring{\href{/「学习总结」数论}{阶}}{阶}}\label{ux9636}
  
  若 \(a \perp n\)，则使 \(a^k \equiv 1 \pmod n\) 成立的 \textbf{最小}
  正整数 \(k\)，称为 \(a\) 模 \(n\) 意义下的阶，记作 \(\text{ord}_n(a)\)。
  可以发现若 \(g\) 为模 \(n\) 意义下原根，那么
  \(\operatorname{ord}_n(g) = \varphi(n)\)。
  
  \subsection{\texorpdfstring{整数模 \(n\)
  乘法群}{整数模 n 乘法群}}\label{ux6574ux6570ux6a21-n-ux4e58ux6cd5ux7fa4}
  
  \subsubsection{定义}\label{ux5b9aux4e49}
  
  对于 \textbf{任意} 一个正整数 \(n\) ，\(1 \sim n\) 中与 \(n\) 互质的
  \(\varphi(n)\) 个数字组成的集合记作 \(\mathbb{Z}^*_n\)。
  
  事实上，由 \(\mathbb{Z}_n^*\) 和模 \(n\) 意义下的乘法组成的代数系统
  \((\mathbb{Z}^*_n, \times )\)
  是一个\href{/「学习总结」群\%20置换群}{群}。
  
  这一点可以考虑 \(\mathbb{Z}^*_n\)
  中元素所包含的质因子，可以发现是显然的。
  
  因为任意一个处于 \(n​\) 的剩余系中且不与 \(n​\) 互质的元素
  \(x​\)，都可以除掉 \(\gcd(x, n)​\) 放到 \(\frac{n}{\gcd(n, x)}​\)
  的剩余系内考虑，所以这里只讨论 \(n​\) 的剩余系中与 \(n​\)
  互质的元素组成的集合，即 \(\mathbb{Z}_n^*​\)（称其为 \(n​\)
  的简化剩余系），当然也因为 \st{我不会} \(\mathbb{Z}_n^*​\)
  的性质实在是太美了。
  
  \subsubsection{离散对数}\label{ux79bbux6563ux5bf9ux6570}
  
  若 \(n\) 存在原根，取任意一个 \(n\) 的原根 \(g\) ，则对于
  \(\mathbb{Z}^*_n\) 中的一个每个元素 \(x\) ，都存在唯一的
  \(k \in [0, \varphi(n)-1]\) ，使得 \(g^k =x​\)。
  
  可以得出 \([0, \varphi(n)-1] \cap \mathbb{Z}\) 中的元素与
  \(\mathbb{Z}_n^*\) 中的元素之间一一对应。
  
  可以建立函数 \(f(x)\) 表示 \(\mathbb{Z}_n^*\) 向
  \([0, \varphi(n)-1] \cap \mathbb{Z}\) 的映射。可以形象的称 \(f(x)\) 为
  \textbf{离散对数}。这里满足很多实数定义下对数的性质。需要注意离散对数间的运算是定义在
  \(\mod \varphi(n)\) 意义下的。
  
  \subsubsection{原根不存在的剩余系下离散对数的定义}\label{ux539fux6839ux4e0dux5b58ux5728ux7684ux5269ux4f59ux7cfbux4e0bux79bbux6563ux5bf9ux6570ux7684ux5b9aux4e49}
  
  离散对数的取值依赖于原根的选取，所以只有 \(n​\) 存在原根时，
  \(\mathbb{Z}_n^*​\) 中的元素才存在 \textbf{直接的} 的离散对数。
  
  可以利用类似于中国剩余定理的一般思想，将 \(n​\)
  分解为质数幂的形式，分别求出 \(x​\) 在每个 \(p_i^k​\) 剩余系下的离散对数
  \(a_i​\)，则可以用 \((a_0, a_1, a_2,\cdots )​\) 这样的 “坐标” 来类似地定义
  \(x​\) 在 \(n​\) 剩余系下的 “离散对数”。根据中国剩余定理，可以发现这样的
  “坐标” 是能够实现和原数一一对应的。
  
  可以先考虑原根存在的 \(\mathbb{Z}_n^*​\)，对 \(\mathbb{Z}_n^*​\)
  中的每一个元素取离散对数（不妨设这里的原根取最小的原根）放入一个集合
  \(G​\)，然后重新定义群 乘法运算为模 \(\varphi(n)​\) 意义下的
  \textbf{加法}，这样 \((G, \times)​\) 也能够形成一个群。不妨用 \(G_n​\)
  来表示这个群。
  
  类似地定义原根不存在的 \(\mathbb{Z}_m^*\)，设
  \(m=\prod_{i=1}^{s}\limits{P_i^{e_i}}\) 。
  
  他们的 “离散对数” 形成的群可以表示为
  \(G_{P_1^{e_1}}\times G_{P_2^{e_2}} \times G_{P_3^{e_3}}\times\cdots\times G_{P_s^{e_s}}\)
  ，其中 \(\times​\) 为定义在群上的直积。
  
  值得一提的是：可以发现，两个群做直积，得到的群的阶为之前两个群的阶的乘积，可以发现，这和欧拉函数的积性是相符的。
  
  这好像没有什么用，只是可以帮助理解或者得到一些小结论吧。
  
  \subsubsection{\texorpdfstring{模 \(2^k(k>2)\)
  意义下的离散对数}{模 2\^{}k(k\textgreater2) 意义下的离散对数}}\label{ux6a21-2kk2-ux610fux4e49ux4e0bux7684ux79bbux6563ux5bf9ux6570}
  
  注意到，\(2^k(k>2)\) 也是没有原根的。
  
  定义 \(2^k (k > 2)​\) 意义下的 “离散对数” 需要如下两个结论
  
  \[
  \operatorname{ord}_{2^k}(5)=2^{k-2}
  \]
  
  而且对于任意一个 \(2^k\) 的简化剩余系下能表示成形如 \(5^\alpha\) 的元素
  \(x\)，\(-x\) 一定不能表示成形如 \(5^\alpha​\) 的元素。
  
  \textbf{一个栗子}
  
  当 \(k=4\) 时，即 \(16=2^4\)。
  
  \(\mathbb{Z}_{16}^*=\{1, 3, 5, 7, 9, 11, 13, 15\}\)
  
  \(5^0=1, 5^1=5, 5^2=9, 5^3=13, 5^4=1\)
  
  \(\operatorname{ord}_{16}(5)=4=2^{k-2}=2^2\)
  
  且 \(-1\equiv 15, -5\equiv 11, -9\equiv 7, -15\equiv 2\)
  这些数字都没有在上面出现过。
  
  简单来说就是 \(2^k\) 的简化剩余系下（大小为
  \(2^{k-1}\)），有恰好一半的数字可以表示成
  \(5^\alpha \mod 2^k\)，恰好一半不可以，这两部分元素一一对应，互为剩余系下的相反数。
  
  所以，可以把模 \(2^k (k>2)\) 意义下的循环群看成是两个原根为 \(5\) 和
  \(-1\) 的乘法群的直积。
  
  其中的元素 \(x​\) 的离散对数形如 \((a, b)​\) 表示 \(5^a \times (-1)^b​\)。
  
  \subsubsection{从乘法群的角度考虑原根和阶}\label{ux4eceux4e58ux6cd5ux7fa4ux7684ux89d2ux5ea6ux8003ux8651ux539fux6839ux548cux9636}
  
  对于任意正整数 \(n​\) ，\(n​\) 的简化剩余系中的取任意一个数字 \(x​\)。
  
  设 \(S_x=\{x^0, x^1, x^2,\cdots\}\) ，可以发现如果定义集合 \(S\)
  的乘法运算为模 \(n\) 意义下的乘法，那么这东西就是
  \((\mathbb{Z}_n^*, \times)\) 的一个子群…这里 \(|S_x|\) （群
  \((S_x, \times)\) 的阶）就可以称为 \(x\) 在模 \(n\) 意义下的阶。
  
  把剩余系的环和群的环结合着理解一下，可以发现这个定义和原先的定义是等价的。
  
  根据这个东西，不难发现： \[
  |S_x|=\frac{\varphi(n)}{\gcd(f(x), \varphi(n))}
  \]
  
  这里的 \(f(x)​\) 为 \(x​\) 在任意原根意义下的离散对数。
  
  存在一个显然的事实：一个常数 \(x​\) 的所有倍数模 \(m​\) 能够取到所有形如
  \(k\cdot\gcd(x, m)​\) 的数（\(k \in \mathbb{Z^*}​\)）。
  
  从 \(n\) 的某个原根意义下离散对数的角度考虑， \(S_x\) 可以看作
  “所有离散对数为 \(\gcd(f(x), \varphi(n))\) 的倍数的元素”
  组成的集合，这样的数字显然有
  \(\frac{\varphi(n)}{\gcd(f(x), \varphi(n))}​\) 个，也就是循环子群的阶数。
  
  之后的问题中，如果不好考虑某个引理，可以转化为选取一个原根后，对每个元素，求其离散对数，然后扔到一个剩余系环上考虑。即使是关于原根本身的引理，也可以用这样的方法证明。
  
  可以发现，我们想要的原根 \(x\)，满足 \(x\)
  的循环子群能够取遍原来群中所有元素，即 \(f(x) \perp \varphi(n)\) 。
  
  考虑一下原根的数量，对于任意一个正整数 \(n\) ，其简化剩余系阶为
  \(\varphi(n)\) ，每个数字取离散对数，指数和 \(\varphi(n)\)
  互质的即可成为原根，这样的数字有 \(\varphi(\varphi(n))\)
  个。事实上，这是原根数量的精确值。
  
  对于 \textbf{任意} 一个正整数 \(n\) ，若其剩余系存在原根，则原根数恰好为
  \(\varphi(\varphi(n))\).
  
  \subsection{实现上的相关问题}\label{ux5b9eux73b0ux4e0aux7684ux76f8ux5173ux95eeux9898}
  
  什么求原根、求阶和求离散对数之类的人间烟火，可以查看
  \href{/「学习总结」数论}{「学习总结」数论}
  
  \subsection{相关栗题}\label{ux76f8ux5173ux6817ux9898}
  
  \subsubsection{debris}\label{debris}
  
  给定素数 \(P\)，求满足 \(1 \le n, m\le P(P-1)\) 且
  \(n^m \equiv m^n \pmod{P}\) 的数对 \((n, m)\) 个数。
  
  答案对素数 \(M\) 取模。 数据组数
  \(T \le 100, P \le 10^{12}, M \le 10^9​\)
  
  如果 \(n, m\) 一个为 \(P\)
  的倍数，另一个不是，那么显然这些方案都不合法。
  
  分两种情况：
  
  如果 \(n, m\) 都是 \(P\) 的倍数，那么这一部分的贡献是平凡的，就是
  \((P-1)^2\)。
  
  如果 \(n, m\) 都不是 \(P\) 的倍数，可以取其离散对数：
  
  \[
  \begin{aligned}
  n^m &\equiv m^n \pmod{P} \\
  \Rightarrow\ g^{am} &\equiv g^{bn} \pmod{P} \\
  \Rightarrow\ am &\equiv bn \pmod{\varphi(P)} \\
  \Rightarrow\ ad &\equiv bc \pmod{P-1}
  \end{aligned}
  \]
  
  定义 \(n=(a, c),m=(b, d)\)。任何一个数字 \(n,m\) 都可以用形如 \((x, y)\)
  的数对表示。
  
  同时\(\forall x,y \in [0, P-2]\ \ (x, y)\) 的数对都唯一的对应一个在
  \([1, P(P-1)]\) 的数字。
  
  原式化简： \[
  \begin{aligned}
  n^m &\equiv m^n \pmod{P} \\
  \Rightarrow\ g^{am} &\equiv g^{bn} \pmod{P} \\
  \Rightarrow\ am &\equiv bn \pmod{\varphi(P)} \\
  \Rightarrow\ ad &\equiv bc \pmod{P-1}
  \end{aligned}
  \]
  
  问题转化为：
  
  若 \(a, b, c, d\) 可以在 \([0, P-1)\) 内任取 ，方程
  \(ad\equiv bc \pmod{P-1}\) 的解 \((a, b, c, d)\) 的数量。
  
  根据乘法群的理论，把 \((\mathbb{Z}_{P-1}^*, \times)\) 拆分成多个 \(p^k\)
  的群的直积。“坐标” 每一维行为独立。
  
  分别求出每一个 \(ad\equiv bc \pmod{p^k}\) 的解数量相乘即可。
  
  考虑如何求出形如 \(ab\equiv bc \pmod{p^k}\) 的方程解数量。
  
  仍然可以分两种情况：
  
  \begin{itemize}
  \tightlist
  \item
    方程两边都与 \(p​\)
    互质，这样答案也是平凡的可以考虑其中三个数字任取，然后最后一个数字算逆元即可，答案就是
    \(\varphi(p^k)^3​\)。
  \item
    方程两边与 \(p\) 不互质，可以考虑方程一边的取值个数，考虑枚举 \(a, b\)
    中 \(p\)
    的次数，同时除去这个值，转化为互质的情况。需要注意如果其次数和大于
    \(p^k\) 两边 \(p\) 的幂次没必要相等。
  \end{itemize}
  
  \subsubsection{子}\label{ux5b50}
  
  求 \(x^k \bmod m\) (\(x\) 为非负整数)的不同值个数，答案对 \(10^9 + 7\)
  取模。
  
  \(m=\prod_{i=1}^{m_s}\limits{p_i^{a_i}}\)
  
  \(k=\prod_{i=1}^{k_s}\limits{q_i^{b_i}}\)
  
  \(m_s, k_s\le 2\times 10^5, p_i,q_i \le10^7, 1\le a_i,b_i \le 10^9\)
  
  下辈子再学。
  
  \subsubsection{\texorpdfstring{\href{https://www.luogu.com.cn/problem/P5605}{小A与两位神仙}}{小A与两位神仙}}\label{ux5c0faux4e0eux4e24ux4f4dux795eux4ed9}
  
  给定一个奇质数次幂 \(m\)。
  
  \(n\) 组询问，每组给定 \((x, y)\) 满足 \(x\perp m, y\perp m\)
  
  判定是否存在 \(x^a\equiv y\pmod{m}\)
  
  \(n \le 2\times 10^4,m\le 10^{18}\)
  
  显然求离散对数非常舒服，直接算倍数即可。只可惜 \(m\) 有亿点点大。
  
  但是可以通过离散对数考虑，设 \(u, v\) 分别为 \(x, y\) 的离散对数。
  
  显然我们希望： \[
  t \in \mathbb{Z}\ \ \  \text{s.t.}\ \  ut=v \pmod{\varphi(m)}
  \]
  
  即： \[
  \gcd(u, \varphi(m)) | v
  \] 其等价于： \[
  \gcd(u, \varphi(m)) | \gcd(v, \varphi(m))
  \] 由上面乘法群的推论： \[
  |S_x|=\frac{\varphi(m)}{\gcd(\varphi(m), f(x))}
  \]
  
  于是可以转化为： \[
  \frac{\varphi(m)}{|S_x|} \mid \frac{\varphi(m)}{|S_y|}
  \] 即： \[
  |S_y| \ \ \ \ \ \ |  \ \ \ \ \ \ |S_x|
  \] 所以只需要对原数 \(x, y\) 分别求阶，然后判断
  \(\operatorname{ord}_m(y) | \operatorname{ord}_m(x)\) 即可。
  
  \end{document}
[INFO] [makePDF] LaTeX run number 1
[INFO] [makePDF] LaTeX output
  This is XeTeX, Version 3.141592653-2.6-0.999995 (TeX Live 2023/Debian) (preloaded format=xelatex)
   restricted \write18 enabled.
  entering extended mode
  (.../input.tex
  LaTeX2e <2023-11-01> patch level 1
  L3 programming layer <2024-01-22>
  (.../article.cls
  Document Class: article 2023/05/17 v1.4n Standard LaTeX document class
  (.../[system]
  (.../xcolor.sty
  (.../color.cfg)
  (.../xetex.def)
  (.../[system]
  (.../geometry.sty
  (.../keyval.sty)
  (.../ifvtex.sty
  (.../iftex.sty)))
  (.../amsmath.sty
  For additional information on amsmath, use the `?' option.
  (.../amstext.sty
  (.../amsgen.sty))
  (.../amsbsy.sty)
  (.../amsopn.sty))
  (.../amssymb.sty
  (.../amsfonts.sty))
  (.../unicode-math.sty
  (.../expl3.sty
  (.../l3backend-xetex.def))
  (.../unicode-math-xetex.sty
  (.../xparse.sty)
  (.../l3keys2e.sty)
  (.../fontspec.sty
  (.../fontspec-xetex.sty
  (.../fontenc.sty)
  (.../fontspec.cfg)))
  (.../fix-cm.sty
  (.../ts1enc.def))
  (.../unicode-math-table.tex)))
  (.../lmodern.sty)
  (.../xeCJK.sty
  (.../ctexhook.sty)
  (.../xtemplate.sty)
  (.../xeCJK.cfg))
  (.../upquote.sty
  (.../textcomp.sty))
  (.../microtype.sty
  (.../etoolbox.sty)
  (.../microtype-xetex.def)
  (.../microtype.cfg))
  (.../setspace.sty)
  (.../parskip.sty
  (.../kvoptions.sty
  (.../ltxcmds.sty)
  (.../kvsetkeys.sty)))
  (.../soul.sty
  (.../soul-ori.sty)
  (.../infwarerr.sty)
  (.../etexcmds.sty))
  (.../xeCJKfntef.sty
  (.../ulem.sty))
  (.../bookmark.sty
  (.../hyperref.sty
  (.../kvdefinekeys.sty)
  (.../pdfescape.sty
  (.../pdftexcmds.sty))
  (.../hycolor.sty)
  (.../auxhook.sty)
  (.../nameref.sty
  (.../refcount.sty)
  (.../gettitlestring.sty))
  (.../pd1enc.def)
  (.../intcalc.sty)
  (.../puenc.def)
  (.../url.sty)
  (.../bitset.sty
  (.../bigintcalc.sty))
  (.../atbegshi-ltx.sty))
  (.../hxetex.def
  (.../stringenc.sty)
  (.../rerunfilecheck.sty
  (.../atveryend-ltx.sty)
  (.../uniquecounter.sty)))
  (.../bkm-dvipdfm.def))
  (.../xurl.sty)
  No file input.aux.
  *geometry* driver: auto-detecting
  *geometry* detected driver: xetex
  (.../mt-LatinModernRoman.cfg)
  
  Package hyperref Warning: Rerun to get /PageLabels entry.
  
  (.../omllmm.fd)
  (.../umsa.fd)
  (.../mt-msa.cfg)
  (.../umsb.fd)
  (.../mt-msb.cfg)
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/b/n' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/m/n' instead on input line 87.
  
  [1] [2] [3] [4] [5] (.../input.aux)
  
  LaTeX Font Warning: Some font shapes were not available, defaults substituted.
  
  
  LaTeX Warning: Label(s) may have changed. Rerun to get cross-references right.
  
   )
  Output written on .../input.pdf (5 pages).
  Transcript written on .../input.log.
[INFO] [makePDF] Rerun needed
  Package hyperref Warning: Rerun to get /PageLabels entry.
  LaTeX Warning: Label(s) may have changed. Rerun to get cross-references right.
[INFO] [makePDF] LaTeX run number 2
[INFO] [makePDF] LaTeX output
  This is XeTeX, Version 3.141592653-2.6-0.999995 (TeX Live 2023/Debian) (preloaded format=xelatex)
   restricted \write18 enabled.
  entering extended mode
  (.../input.tex
  LaTeX2e <2023-11-01> patch level 1
  L3 programming layer <2024-01-22>
  (.../article.cls
  Document Class: article 2023/05/17 v1.4n Standard LaTeX document class
  (.../[system]
  (.../xcolor.sty
  (.../color.cfg)
  (.../xetex.def)
  (.../[system]
  (.../geometry.sty
  (.../keyval.sty)
  (.../ifvtex.sty
  (.../iftex.sty)))
  (.../amsmath.sty
  For additional information on amsmath, use the `?' option.
  (.../amstext.sty
  (.../amsgen.sty))
  (.../amsbsy.sty)
  (.../amsopn.sty))
  (.../amssymb.sty
  (.../amsfonts.sty))
  (.../unicode-math.sty
  (.../expl3.sty
  (.../l3backend-xetex.def))
  (.../unicode-math-xetex.sty
  (.../xparse.sty)
  (.../l3keys2e.sty)
  (.../fontspec.sty
  (.../fontspec-xetex.sty
  (.../fontenc.sty)
  (.../fontspec.cfg)))
  (.../fix-cm.sty
  (.../ts1enc.def))
  (.../unicode-math-table.tex)))
  (.../lmodern.sty)
  (.../xeCJK.sty
  (.../ctexhook.sty)
  (.../xtemplate.sty)
  (.../xeCJK.cfg))
  (.../upquote.sty
  (.../textcomp.sty))
  (.../microtype.sty
  (.../etoolbox.sty)
  (.../microtype-xetex.def)
  (.../microtype.cfg))
  (.../setspace.sty)
  (.../parskip.sty
  (.../kvoptions.sty
  (.../ltxcmds.sty)
  (.../kvsetkeys.sty)))
  (.../soul.sty
  (.../soul-ori.sty)
  (.../infwarerr.sty)
  (.../etexcmds.sty))
  (.../xeCJKfntef.sty
  (.../ulem.sty))
  (.../bookmark.sty
  (.../hyperref.sty
  (.../kvdefinekeys.sty)
  (.../pdfescape.sty
  (.../pdftexcmds.sty))
  (.../hycolor.sty)
  (.../auxhook.sty)
  (.../nameref.sty
  (.../refcount.sty)
  (.../gettitlestring.sty))
  (.../pd1enc.def)
  (.../intcalc.sty)
  (.../puenc.def)
  (.../url.sty)
  (.../bitset.sty
  (.../bigintcalc.sty))
  (.../atbegshi-ltx.sty))
  (.../hxetex.def
  (.../stringenc.sty)
  (.../rerunfilecheck.sty
  (.../atveryend-ltx.sty)
  (.../uniquecounter.sty)))
  (.../bkm-dvipdfm.def))
  (.../xurl.sty)
  (.../input.aux)
  *geometry* driver: auto-detecting
  *geometry* detected driver: xetex
  (.../mt-LatinModernRoman.cfg)
  (.../omllmm.fd)
  (.../umsa.fd)
  (.../mt-msa.cfg)
  (.../umsb.fd)
  (.../mt-msb.cfg)
  
  LaTeX Font Warning: Font shape `TU/ARPLUKaiCN(0)/b/n' undefined
  (Font)              using `TU/ARPLUKaiCN(0)/m/n' instead on input line 87.
  
  [1] [2] [3] [4] [5] (.../input.aux)
  
  LaTeX Font Warning: Some font shapes were not available, defaults substituted.
  
   )
  Output written on .../input.pdf (5 pages).
  Transcript written on .../input.log.