定理及扩展（附证明）"/>

欧拉定理及扩展（附证明）

若 ( a , m ) = 1 (a,m)=1 (a,m)=1，则满足 a φ ( m ) ≡ 1 ( m o d m ) a^{\varphi (m)} \equiv 1\ (mod \ m) aφ(m)≡1 (mod m)

证明

设 与 m 互 质 的 数 为 b 1 , b 2 , b 3 , . . . , b φ ( m ) ∵ ( a , m ) = 1 ∴ a b 1 , a b 2 , a b 3 , . . . , a b φ ( m ) 都 与 m 互 质 ， 且 每 个 数 均 不 相 同 ∴ { b 1 , b 2 , b 3 , . . . , b φ ( m ) } 中 ， 每 一 个 数 一 定 与 { a b 1 , a b 2 , a b 3 , . . . , a b φ ( m ) } 中 的 一 个 数 同 余 ， 且 一 一 对 应 。 ∴ a φ ( m ) ∏ i = 1 φ ( m ) b i ≡ ∏ i = 1 φ ( m ) a b i ≡ ∏ i = 1 φ ( m ) b i ( m o d m ) ∴ m ∣ a φ ( m ) ∏ i = 1 φ ( m ) b i − ∏ i = 1 φ ( m ) b i 即 m ∣ ( a φ ( m ) − 1 ) ∏ i = 1 φ ( m ) b i 又 ∵ ( m , ∏ i = 1 φ ( m ) b i ) = 1 ∴ m ∣ a φ ( m ) − 1 即 a φ ( m ) ≡ 1 ( m o d m ) \begin{array}{ll} 设与m互质的数为b_1,b_2,b_3,...,b_{\varphi (m)}\\\\ \because (a,m)=1\\\\ \therefore ab_1,ab_2,ab_3,...,ab_{\varphi (m)} 都与m互质，且每个数均不相同\\\\ \therefore\{b_1,b_2,b_3,...,b_{\varphi (m)}\}中，每一个数一定与\{ab_1,ab_2,ab_3,...,ab_{\varphi (m)}\}中的一个数同余，且一一对应。\\\\ \therefore a^{\varphi (m)}\prod_{i=1}^{\varphi (m)}b_i \equiv \prod_{i=1}^{\varphi (m)}ab_i \equiv \prod_{i=1}^{\varphi (m)}b_i \ (mod\ m)\\\\ \therefore m \mid a^{\varphi (m)}\prod_{i=1}^{\varphi (m)}b_i-\prod_{i=1}^{\varphi (m)}b_i\\\\ 即m \mid (a^{\varphi (m)}-1)\prod_{i=1}^{\varphi (m)}b_i\\\\ 又\because (m,\prod_{i=1}^{\varphi (m)}b_i)=1\\\\ \therefore m \mid a^{\varphi (m)}-1\\\\ 即a^{\varphi (m)} \equiv 1\ (mod \ m) \end{array} 设与m互质的数为b1​,b2​,b3​,...,bφ(m)​∵(a,m)=1∴ab1​,ab2​,ab3​,...,abφ(m)​都与m互质，且每个数均不相同∴{b1​,b2​,b3​,...,bφ(m)​}中，每一个数一定与{ab1​,ab2​,ab3​,...,abφ(m)​}中的一个数同余，且一一对应。∴aφ(m)∏i=1φ(m)​bi​≡∏i=1φ(m)​abi​≡∏i=1φ(m)​bi​ (mod m)∴m∣aφ(m)∏i=1φ(m)​bi​−∏i=1φ(m)​bi​即m∣(aφ(m)−1)∏i=1φ(m)​bi​又∵(m,∏i=1φ(m)​bi​)=1∴m∣aφ(m)−1即aφ(m)≡1 (mod m)​

费马小定理

当 p p p为质数，则 a p − 1 ≡ 1 ( m o d p ) a^{p-1} \equiv 1\ (mod\ p) ap−1≡1 (mod p)
因为 p p p为质数时， φ ( p ) = p − 1 \varphi(p)=p-1 φ(p)=p−1

扩展欧拉定理

扩展到不要求互质

当 ( a , m ) = 1 (a,m)=1 (a,m)=1时，
a c ≡ a c m o d φ ( m ) ( m o d m ) a^c \equiv a^{c\ mod\ \varphi(m)}\ (mod\ m) ac≡ac mod φ(m) (mod m)
证明略

当 ( a , m ) ̸ = 1 且 c &lt; φ ( m ) (a,m)\not= 1且c&lt;\varphi(m) (a,m)̸​=1且c<φ(m)时，
a c ≡ a c ( m o d m ) a^c\equiv a^c\ (mod\ m) ac≡ac (mod m)
无需证明

当 ( a , m ) ̸ = 1 且 c ≥ φ ( m ) (a,m)\not= 1且c\geq \varphi(m) (a,m)̸​=1且c≥φ(m)时，
a c ≡ a c m o d φ ( m ) + φ ( m ) ( m o d m ) a^c\equiv a^{c\ mod\ \varphi(m)+\varphi(m)}\ (mod\ m) ac≡ac mod φ(m)+φ(m) (mod m)

证明

取 a 的 质 因 子 p ， 令 m = s × p r ， 且 ( s , p ) = 1 p φ ( s ) ≡ 1 ( m o d s ) ∵ s 不 含 因 子 p ∴ φ ( s ) ∣ φ ( m ) ∴ p φ ( m ) ≡ 1 ( m o d s ) ⟹ p k φ ( m ) ≡ 1 ( m o d s ) ⟹ p k φ ( m ) + r ≡ p r ( m o d s × p r ) ⟹ p k φ ( m ) + r + c ≡ p r + c ( m o d m ) ∵ k , c 为 任 意 非 负 整 数 ∴ 上 式 可 表 述 为 ： 若 整 数 c ≥ r , 则 p c ≡ p k φ ( m ) + c ( m o d m ) 设 a 中 含 有 p 因 子 p k ， c ≥ φ ( m ) ≥ r ( p k ) c ≡ p k c ≡ p k φ ( m ) + k c ≡ ( p k ) φ ( m ) + c ≡ ( p k ) t φ ( m ) + c ( m o d m ) ( t 为 任 意 正 整 数 ) ⟹ ( p k ) c ≡ ( p k ) c m o d φ ( m ) + φ ( m ) ( 加 φ ( m ) 为 了 保 证 最 后 的 指 数 ≥ φ ( m ) ) a 的 每 个 质 因 子 都 满 足 上 式 同 余 式 可 相 乘 ， 乘 起 来 即 为 a c ≡ a c m o d φ ( m ) + φ ( m ) ( m o d m ) \begin{array}{ll} 取a的质因子p，令m=s\times p^r，且(s,p)=1\\\\ p^{\varphi(s)}\equiv 1\ (mod\ s)\\\\ \because s不含因子p\\\\ \therefore \varphi(s)\mid \varphi(m)\\\\ \therefore p^{\varphi(m)}\equiv 1\ (mod\ s)\\\\ \Longrightarrow p^{k \varphi(m)}\equiv 1\ (mod\ s)\\\\ \Longrightarrow p^{k \varphi(m)+r}\equiv p^r\ (mod\ s\times p^r)\\\\ \Longrightarrow p^{k\varphi(m)+r+c}\equiv p^{r+c}\ (mod\ m)\\\\ \because k,c为任意非负整数\\\\ \therefore 上式可表述为：若整数c\geq r ,则p^c\equiv p^{k\varphi(m)+c}\ (mod\ m)\\\\ 设a中含有p因子p^k，c\geq \varphi(m)\geq r\\\\ {(p^k)}^c\equiv p^{kc}\equiv p^{k\varphi(m)+kc}\equiv {(p^k)}^{\varphi(m)+c}\equiv (p^k)^{t\varphi(m)+c}\ (mod\ m)\ (t为任意正整数)\\\\ \Longrightarrow {(p^k)}^c\equiv {(p^k)}^{c\ mod\ \varphi(m)+\varphi(m)}\ \ (加\varphi(m)为了保证最后的指数\geq \varphi(m) )\\\\ a的每个质因子都满足上式\\\\ 同余式可相乘，乘起来即为a^c\equiv a^{c\ mod\ \varphi(m)+\varphi(m)}\ (mod\ m) \end{array} 取a的质因子p，令m=s×pr，且(s,p)=1pφ(s)≡1 (mod s)∵s不含因子p∴φ(s)∣φ(m)∴pφ(m)≡1 (mod s)⟹pkφ(m)≡1 (mod s)⟹pkφ(m)+r≡pr (mod s×pr)⟹pkφ(m)+r+c≡pr+c (mod m)∵k,c为任意非负整数∴上式可表述为：若整数c≥r,则pc≡pkφ(m)+c (mod m)设a中含有p因子pk，c≥φ(m)≥r(pk)c≡pkc≡pkφ(m)+kc≡(pk)φ(m)+c≡(pk)tφ(m)+c (mod m) (t为任意正整数)⟹(pk)c≡(pk)c mod φ(m)+φ(m)  (加φ(m)为了保证最后的指数≥φ(m))a的每个质因子都满足上式同余式可相乘，乘起来即为ac≡ac mod φ(m)+φ(m) (mod m)​

用途

再也不用担心指数爆炸了！！指数也可以取模了

题目

BZOJ3884（推公式）
BZOJ4869（+线段树）