• 初等数论中的欧拉定理

    定理内容


      在数论中,欧拉定理 (也称费马-欧拉定理 ) 是一个关于同余的性质。欧拉定理表明,若n,a为正整数,且n,a互素,(a,n) = 1,则
    a^φ(n) ≡ 1 (mod n)

    证 明


    首先证明下面这个命题:
    对于集合Zn={x1,x2,...,xφ(n)},其中xi(i=1,2,…φ(n))是不 大于n且与n互素的数,即n的一个化简剩余系,或称简系,或称缩系),考虑集合S = {a*x1(mod n),a*x2(mod n),...,a*xφ(n)(mod n)}
    则S = Zn
    1) 由于a,n互质,xi也与n互质,则a*xi也一定于n互质,因此
    任意xi,a*xi(mod n) 必然是Zn的一个元素
    2) 对于Zn中两个元素xi和xj,如果xi ≠ xj
    则a*xi(mod n) ≠ a*xj(mod n),这个由a、n互质和消去律可以得出。
    所以,很明显,S=Zn
    既然这样,那么
    (a*x1 × a*x2×...×a*xφ(n))(mod n)
    = (a*x1(mod n) × a*x2(mod n) × ... × a*xφ(n)(mod n))(mod n)
    = (x1 × x2 × ... × xφ(n))(mod n)
    考虑上面等式左边 和右边
    左边等于([a^φ(n)] *(x1 × x2 × ... × xφ(n))) (mod n)
    右边等于x1 × x2 × ... × xφ(n))(mod n)
    而x1 × x2 × ... × xφ(n)(mod n)和n互质
    根据消去律,可以从 等式两边约去,就得到:
    a^φ(n) ≡ 1 (mod n)
    推论:对于互质的数a、n,满足a^(φ(n)+1) ≡ a (mod n)
    费 马定理 :
    a是不能被质 数 p整 除 的正整数,则有a^(p-1) ≡ 1 (mod p)
    证明这个定理非常简单,由于φ(p) = p-1,代入欧拉定理即可证明。
    同 样有推论:对于不能被质数p整除的正整数a,有a^p ≡ a (mod p)