2.4 Euler’s theorm

Euler’s theorm

a^p-1≡1  mod p    其中p為質數     1<a<p

   

General Version of Euler’s theorm

aØ(N) ≡1   mod N    其中 N為正整數   1<a<N

Ø(N)為Euler function   即小於N且與N互質的整數個數

例如：
   Ø(5):4    (1、2、3、4)

   Ø(8):4    (1、3、5、7)

   Ø(10):4    (1、3、7、9)

   Ø(11):10    (1、2、3、4、5、6、7、8、9、10)

由以上可以得到

(1)   Ø(P) = P-1    其中P為質數

(2)   Ø(N)=(P-1) (q-1)     其中p、q為相異質數  N=p xq

證明：　　

         N=p xq

　　小於N與N不互質的正整數為 p、2p、3p..、(q-1)p  共(q-1)個

　　                                                   q、2q、3q..、(p-1)q  共(p-1)個

        小於N與N互質的正整數個數

         (N-1)-(p-1)-(q-) = pq-1-p-q+2 =(P-1) (q-1)

     Ø(N)=(P-1) (q-1)