フェルマーの小定理

ｐを素数、aを任意の整数とするとき

a^p-1-1=0 (modp)

例:　17は素数なので、1^16-1,2^16-1,3^16-1,・・・,16^16-1,18^16-1,・・・

はすべて17の倍数である。

たとえば、16^16-1=18446744073709551615を17で割ると、1085102571150095

17^16-1は17で割り切れない。17の倍数である17^16より1小さいため17の倍数ではありえない

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

オイラーの定理

(a,n)=1のとき、

a^φ(n)-1-1=0 (modｎ)

ｐ、ｑを素数,n=pqとするとφ(n)=(p-1)(q-1)

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝