欧拉定理

2019-04-14 19:45发布

站内文章 / 模拟电子
11178 0 1156
  • 前置技能
    • 剩余系和剩余类
      • 定义1" role="presentation">1(剩余类)：设m" role="presentation">m为自然数，称为模，所有对m" role="presentation">m同余的整数所组成的集合叫做模m" role="presentation">m的一个剩余类，如果一个剩余类中的数和模数m" role="presentation">m是互素的，那么就称它为模m" role="presentation">m的一个互素剩余类。
      • 定义2" role="presentation">2(剩余系)：在每一个剩余系Kγ(0≤γ≤m−1)" role="presentation">Kγ(0≤γ≤m−1)中任取一数aγ" role="presentation">aγ，我们把a0,a1,…,am−1" role="presentation">a0,a1,…,am−1叫做模m" role="presentation">m的一个完全剩余系；在每一个互素剩余类Kγ（0≤γ≤m−1,(γ,m)=1）" role="presentation">Kγ（0≤γ≤m−1,(γ,m)=1）中任取一数aγ" role="presentation">aγ，则所有的aγ" role="presentation">aγ称为模m" role="presentation">m的一个互素（简化）剩余系。
      • 定理1" role="presentation">1：设m" role="presentation">m为自然数，K,l" role="presentation">K,l为任意数且(K,m)=1" role="presentation">(K,m)=1，则当x" role="presentation">x通过m" role="presentation">m的完全系时，Kx+l" role="presentation">Kx+l也通过m" role="presentation">m的一个完全系。
      • 定理2" role="presentation">2：设m" role="presentation">m为自然数，K,l" role="presentation">K,l为任意数且(K,m)=1" role="presentation">(K,m)=1，则当x" role="presentation">x通过m" role="presentation">m的简化系时，Kx+lm" role="presentation">Kx+lm也通过m" role="presentation">m的一个简化系。
  • 欧拉定理表达式aφ(m)≡1(modm)((a,m)=1)" role="presentation">aφ(m)≡1(modm)((a,m)=1)
  • 证明
    欧拉定理的证明需要用到的是上述定理中的定理2。
    设x1,x2,…,xφ(m)" role="presentation">x1,x2,…,xφ(m)是模m" role="presentation">m的一个简化系，因为(a,m)=1" role="presentation">(a,m)=1，由定理2可知ax1,ax2,…,axφ(m)" role="presentation">