Euler-Fermat 定理

Euler-Fermat 定理的研究源于 Fermat 提出的一个猜想：若 $p$为素数，$(a, p) = 1$，则$a^{p-1} \equiv 1 \pmod{p}$。这个猜想被 Euler 证明，称为 Fermat 小定理。Euler 还将其做了推广，就是著名的 Euler-Fermat 定理。

内容

设$m \in \mathbb{N}$，$(a, m) = 1$，则$a^{\varphi (m)} \equiv 1 \pmod{m}.$

证明

由 原根 这里阶的概念可以知道，有 $a^{b}\equiv 1{\pmod {m}}$，并且 $b|\varphi (m)$，则有 $a^{\varphi(m)} \equiv 1 \pmod m$。

应用

1. 可以用来求解逆元，由费马小定理可知：若 $p$为素数，$(a, p) = 1$，则$a^{p-2}\equiv a^{-1}{\pmod {p}}$。

引入原根

这个定理表明，在$\Z_m^*$中，一定存在$r$，使得$\overline{a^r} = \bar{1}$，而$\Z_m^*$具有循环群结构，故元素$a$经过有限次自乘后又回到了本身，如果这个元素自乘能得到全部元素，那对研究这个群的结构是十分有用的，这就是我们后面要引入的原根概念。

上下节

• 上一节：数论函数的卷积
• 下一节：原根