欧拉定理

  • 前置技能

    • 剩余系和剩余类
      • 定义1(剩余类):设m为自然数,称为模,所有对m同余的整数所组成的集合叫做模m的一个剩余类,如果一个剩余类中的数和模数m是互素的,那么就称它为模m的一个互素剩余类。
      • 定义2(剩余系):在每一个剩余系Kγ(0γm1)中任取一数aγ,我们把a0,a1,,am1叫做模m的一个完全剩余系;在每一个互素剩余类Kγ0γm1,(γ,m)=1中任取一数aγ,则所有的aγ称为模m的一个互素(简化)剩余系。
      • 定理1:设m为自然数,K,l为任意数且(K,m)=1,则当x通过m的完全系时,Kx+l也通过m的一个完全系。
      • 定理2:设m为自然数,K,l为任意数且(K,m)=1,则当x通过m的简化系时,Kx+lm也通过m的一个简化系。
  • 欧拉定理表达式

    aφ(m)1(modm)((a,m)=1)
  • 证明
    欧拉定理的证明需要用到的是上述定理中的定理2。

    x1,x2,,xφ(m)
    是模m的一个简化系,因为(a,m)=1,由定理2可知
    ax1,ax2,,axφ(m)
    也是通过模m的一个简化系。所以有
    (ax1)(ax2)(axφ(m))x1x2xφ(m)(modm)
    因为
    (x1x2xφ(m),m)=1
    所以我们得到
    aφ(m)1(modm)
    证毕.
;