欧拉定理 & 费马小定理

费马小定理

定义

为素数,,则

另一个形式:对于任意整数 ,有

证明

设一个质数为 ,我们取一个不为 倍数的数

构造一个序列:,这个序列有着这样一个性质:

证明:

又因为每一个 都是独一无二的,且

得证(每一个 都对应了一个 )

, 则

证毕。

也可用归纳法证明:

显然 ,假设 成立,那么通过二项式定理有

因为 对于 成立,在模 意义下 ,那么 ,将 带入得 得证。

欧拉定理

在了解欧拉定理(Euler's theorem)之前,请先了解 欧拉函数。定理内容如下:

定义

,则

证明

实际上这个证明过程跟上文费马小定理的证明过程是非常相似的:构造一个与 互质的数列,再进行操作。

为模 意义下的一个简化剩余系,则 也为模 意义下的一个简化剩余系。所以 ,可约去 ,即得

为素数时,由于 ,代入欧拉定理可立即得到费马小定理。

扩展欧拉定理

定义

解释

读者可能对第二行产生疑问,这一行表达的意思是:如果 的话,就不能降幂了。

主要是因为题目中 不会太大,而如果 ,自然复杂度是可以接受的。而如果 的话,复杂度可能就超出预期了,这个时候我们才需要降幂来降低复杂度。

证明

直观理解

fermat1

需要知道的是,在 的条件下, 的取值范围一定在 ,而 ,那么对于任意一个数 ,那么很容易就能知道它的 后继,在有限的空间内这一定会形成一个循环。

在扩展欧拉定理中,循环分为纯循环和混循环。其中纯循环中不存在节点有两个前驱,而混循环则反之。而 形成的序列可以是一个混循环,那么只需要知道循环节的长度,和前面那一小段未进入循环节的长度,就可以根据这个性质来进行降幂了。

值得注意的是,无论是费马小定理,还是(扩展)欧拉定理,一个很重要的应用就是降幂,从而将不可能的表达式化为可能。

形式证明

证明转载自 synapse7,并进行了一些整理。

  1. 命题 的从 次, 次到 次幂模 构成的序列中,存在 ,使得前 个数(即从 ) 互不相同,从第 个数开始,每 个数就循环一次。

    证明

    • 由鸽巢定理易证。

      我们把 称为 幂次模 的循环起始点, 称为循环长度。(注意: 可以为

      用公式表述为:

  2. 命题 为素数的情况,该式成立。

    证明

    • 若模 不能被 整除,而因为 是一个素数,那么 成立,根据欧拉定理,容易证明该式成立。

    • 若模 能被 整除,那么存在 使得 ,且 成立。所以根据欧拉定理有

      又由于 ,所以根据欧拉函数的求值规则,容易得到:,即我们有:

      所以 ,即 ,两边同时乘以 ,得 (因为

      所以对于 中素因子 的次数 满足:。我们可以简单变换形式,得到 推论

      又由于 ,所以 (tips: 是素数,最小是 ,而 )。

      所以因为 ,故有:

      所以

  3. 命题 为素数的幂的情况,该式成立。

    证明

    • 不妨令 ,是否依然有

      答案是肯定的,由命题 1 可知存在 使得 ,所以 ,所以令 时,我们能有

      此时有关系:,且 ,由 的关系,依然可以得到

  4. 合数 为合数的情况,该式成立。

    证明

    • 只证 拆成两个素数的幂的情况,大于两个的用数学归纳法可证。

      ,其中 ,而 的循环长度为

      ,由于 ,那么 ,所以

      的关系,依然可以得到

      证毕。

习题

  1. SPOJ #4141 "Euler Totient Function"[Difficulty: CakeWalk]
  2. UVA #10179 "Irreducible Basic Fractions"[Difficulty: Easy]
  3. UVA #10299 "Relatives"[Difficulty: Easy]
  4. UVA #11327 "Enumerating Rational Numbers"[Difficulty: Medium]
  5. TIMUS #1673 "Admission to Exam"[Difficulty: High]

评论