欧拉定理和循环节

· · 个人记录

> 显然有一个循环节是 n, 因为 $A_{n + 1}$ 一定会和 $A_{1 \to n}$ 其中一个相同 （各朝园里） > 我们考虑具体的问题， $A_i = (A_{i - 1} + a)$,根据同余，$\because A_i \equiv A_{i - 1} + a (\mod n)\ \therefore A_i = A_{i - 1} + a - k * n

我们再将 A_{i - 1} 化简，可以得到 A_{i} = c * a - k * n, 可以知道 a\mid A_i 所以 (a,n) \mid A_i,我们用 d = (a,n) 来表示

可以发现，随着 i 的增大，就是一个不断遍历 d 的过程，所以我们就相当于是看 n 中总共有几个 d，所以 \color{red}\text{具体循环节 = } \frac{n}{(a,n)}

例题： ax\equiv b(mod\space n) 中 x 落在 [1,n] 的个数

首先考虑，随着 x 的增大，也就是相当于每一次都加了一个 a

同之前的想法设 d = (a,n)，也就是随着 x 的增大， LHS 不断在遍历 d 的倍数，如果 d \nmid b 说明不会有解，所以直接输出 0

之后考虑有解的情况，也就是 d \mid b，因为 b 的取值是唯一的，所以在每一段的循环中只会出现一次，所以原题相当于在 x\in[1,n] 中总共有几个循环节，所以 ans = \frac{n}{\frac{n}{(a,n)}} = (a,n)

综上：

\begin{cases} ans = 0,\ d \nmid b\\ ans = (a,n),\ d\mid b\\ \end{cases} > 如果 $n$ 是质数，可以用欧拉定理，我们先排除 $(a,n) \neq 1$ 的情况 > 如果有循环节那么，$A_{i} \equiv A_{i + s} (\mod n)$, $\because (a,n) = 1, \therefore (a^c, n) = 1$，所以我们对同余方程两边同时 $\div a^r$ 可以得到, $a^s \equiv 1 (\mod n)$,根据费马小定理 $a^{p} \equiv p (\ mod p) \to a^{p - 1} \equiv 1 (\mod p)$ 所以，解就是 $n - 1

所以当 n 为 p 的时候，ans = n - 1

如果 n 不是质数呢 ?

先来看看扩展欧拉定理：

a^c \equiv 1 (\mod n) a^ c \equiv \begin{cases} a ^ {c \mod \varphi(n)}, \gcd(a, n) = 1 \\ a ^ c, \gcd(a,n) \neq 1,c < \varphi(n) \\ a ^ {(c \mod \varphi(n)) + \varphi(n)}, \gcd(a,n) \neq 1, c \ge \varphi(n) \end{cases}

我们可以考虑将 n 表示成 n = \prod p_i^{q_i} 的形式，根据算数基本定理，这种表示方式是唯一的

个人认为扩展欧拉定理可能是先发现循环节的长度的。

s 为循环节的长度

考虑 a^i \mod m 最多只有 m 种结果，根据鸽巢原理，可以知道必定会出现循环节

a^0, a^1 ... a^r, a^{r + 1} .. a ^{r + s - 1}, a^r \mod m

所以可以发现 a^0 ... a^{r - 1} 是没有重复的

可以发现 m \mid a^r(a^s - 1) 不妨假设 m = m_0 * a^r, (a, m_0) = 1

所以 m_0 \mid (a^s - 1), a^s \equiv 1 \pmod {m_0}

\because (a, m_0) = 1 \therefore a^{\varphi(m_0)} \equiv 1 \pmod {m_0} \Rightarrow s \mid \varphi(m_0), \varphi(m_0)\mid \varphi(m)

所以之前的结论可以表示为 a^0, a^1 ... a^r....a^{r + \varphi(m) - 1}, a^r

循环节的长度为 \varphi(m)

考虑到，从 r 开始的循环节不包含 0 \to r - 1 所以还要取模

参考文章:循环节与拓展欧拉定理（广义欧拉降幂）