跳转至

欧拉定理 & 费马小定理

费马小定理

定义

p 为素数,gcd(a,p)=1,则 ap11(modp)

另一个形式:对于任意整数 a,有 apa(modp)

证明

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

构造一个序列:A={1,2,3,p1},这个序列有着这样一个性质:

i=1p1 Aii=1p1(Ai×a)(modp)

证明:

(Ai,p)=1,(Ai×a,p)=1

又因为每一个 Ai×a(modp) 都是独一无二的,且 Ai×a(modp)<p

得证(每一个 Ai×a 都对应了一个 Ai

f=(p1)!, 则 fa×A1×a×A2×a×A3×Ap1(modp)

ap1×ff(modp)ap11(modp)

证毕。

也可用归纳法证明:

显然 1p1(modp),假设 apa(modp) 成立,那么通过二项式定理有

(a+1)p=ap+(p1)ap1+(p2)ap2++(pp1)a+1

因为 (pk)=p(p1)(pk+1)k! 对于 1kp1 成立,在模 p 意义下 (p1)(p2)(pp1)0(modp),那么 (a+1)pap+1(modp),将 apa(modp) 带入得 (a+1)pa+1(modp) 得证。

欧拉定理

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

定义

gcd(a,m)=1,则 aφ(m)1(modm)

证明

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

r1,r2,,rφ(m) 为模 m 意义下的一个简化剩余系,则 ar1,ar2,,arφ(m) 也为模 m 意义下的一个简化剩余系。所以 r1r2rφ(m)ar1ar2arφ(m)aφ(m)r1r2rφ(m)(modm),可约去 r1r2rφ(m),即得 aφ(m)1(modm)

m 为素数时,由于 φ(m)=m1,代入欧拉定理可立即得到费马小定理。

扩展欧拉定理

定义

ab{abmodφ(m),gcd(a,m)=1,ab,gcd(a,m)1,b<φ(m),a(bmodφ(m))+φ(m),gcd(a,m)1,bφ(m).(modm)

解释

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

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

证明

直观理解

fermat1

需要知道的是,在 (modm) 的条件下,abmodm 的取值范围一定在 [0,m),而 aimodm=(ai1modm)×amodm,那么对于任意一个数 a,那么很容易就能知道它的 后继,在有限的空间内这一定会形成一个循环。

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

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

形式证明

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

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

    证明

    • 由鸽巢定理易证。

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

      用公式表述为:ir,aiai+s(modm)

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

    证明

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

    • 若模 m 能被 a 整除,那么存在 rm 使得 m=arm,且 gcd(a,m)=1 成立。所以根据欧拉定理有 aφ(m)1(modm)

      又由于 gcd(ar,m)=1,所以根据欧拉函数的求值规则,容易得到:φ(m)=φ(m)×(a1)ar1,即我们有:φ(m)φ(m)

      所以 aφ(m)1(modm),φ(m)φ(m)aφ(m)1(modm),即 aφ(m)=km+1,两边同时乘以 ar,得 ar+φ(m)=km+ar(因为 m=arm

      所以对于 m 中素因子 a 的次数 r 满足:arar+φ(m)(modm)。我们可以简单变换形式,得到 推论

      b>rabar+((br)modφ(m))(modm)

      又由于 m=arm,所以 φ(m)=φ(ar)φ(m)φ(ar)=ar1(a1)r(tips:a 是素数,最小是 2,而 r1)。

      所以因为 φ(m)r,故有:

      arar+φ(m)armodφ(m)+φ(m)(modm)

      所以

      abar+(br)modφ(m)armodφ(m)+φ(m)+(br)modφ(m)aφ(m)+bmodφ(m)(modm)

      ababmodφ(m)+φ(m)(modm)

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

    证明

    • 不妨令 a=pk,是否依然有 r,arar+φ(m)(modm)

      答案是肯定的,由命题 1 可知存在 s 使得 as1(modm),所以 plcm(s,k)1(modm),所以令 s=sgcd(s,k) 时,我们能有 psk1(modm)

      此时有关系:sssφ(m),且 r=rkrφ(m),由 r,sφ(m) 的关系,依然可以得到 ababmodφ(m)+φ(m)(modm)

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

    证明

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

      a=a1a2,其中 ai=piki,而 ai 的循环长度为 si

      slcm(s1,s2),由于 s1φ(m),s2φ(m),那么 lcm(s1,s2)φ(m),所以 sφ(m)r=max(riki)max(ri)φ(m)

      r,sφ(m) 的关系,依然可以得到 ababmodφ(m)+φ(m)(modm)

      证毕。

习题

  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]