次に、フェルマーの小定理を証明する
整数aに対し、a^p＝（1+a）^p＝ΣpCka^k　（k=0-p）
ここで、pCkはk=0,pの場合を除いてpの倍数である　pCk＝p!/k!(p-k)！で、pが素数ならk!、（p-k）！はpの倍数でない
よってa^p＝1^p＋（a-1）^p+（pの倍数）
ここで、（a-1）^pにも同じ操作を繰り返すと（a-1）^p＝1+（a-2）^p+（pの倍数）
これを繰り返すと、a^p＝a+（pの倍数）
aとpが互いに素であるならば、aX＝aY（modp）のときX＝Y（modp）が成立するため
（a-1）^p＝1+（pの倍数）
よってフェルマーの小定理：「a^（p-1） をpで割った余りは 1」が証明された