注：本文不写证明。
一、剩余类环 \(\mathbb{Z}/n\mathbb{Z}\)
记号：\(\overline{x}\) 在\(\mod n\) 意义下代表一个集合：\(\{\dots,x-2n,x-n,x,x+n,x+2n,\dots\}\)
加法逆元：\(a: \overline{-a} \text{ or }\overline{n-a}\)
乘法逆元：\(\overline{a}\times \overline{b} = 1\)
费马小定理
\[a^{p-1}=1(\bmod p, 0 < a < p) \]Euler's Theorem / 费马小定理推广：
\[a^{\varphi(p)}=1(\bmod p) \]Quiz
计算: \(3^{\left(3^{100}\right)} \bmod 100\)。
使用 Euler's Theorem 需要算出 \(\varphi\)，计算得 \(\varphi(100)=40,\varphi(40)=16\)。
\(\displaystyle 3^{\left(3^{100}\right)} \bmod 100=3^{3^{100} \bmod 40}=3^{3^{100 \bmod 16}}=3^{81}=3^{1}=3\)
\(\varphi\) 函数
Lemma 1：若 \(n \bmod p = 0\)，则 \(\varphi(pn)=p\varphi(n)\)。
Lemma 2：若 \(n \bmod p \neq 0\)，则 \(\varphi(pn) = (p - 1)\varphi(n)\)。
空：\(\varphi(n)\) 公式。
Example
\(\varphi(60) = \varphi(4) \times \varphi(3) \times \varphi(5) = 2 \times 2 \times 4=16\)。
HW1：
\[\sum_{d | n}\varphi(d) = n \]二、扩展 Euclid
此算法可以计算形如 \(ax+by=\gcd(a,b)\) 的解。
三、原根
在 \(\bmod n\) 意义下的原根数量是 \(\varphi(\varphi(n))\)。
Problem
给定 \(n\)，求 \(n\) 的一个原根。
考虑随机化，单次的成功率是 \(\displaystyle \frac{\varphi(\varphi(n))}{n}\)，所以期望步数为 \(\dfrac{n}{\varphi(\varphi(n))}\)。
空缺：如何判定。
指标
BSGS, Baby Step Giant Step 算法
