フェルマーの小定理

  • 公開日時: 2017/02/19 19:41
  • 閲覧数: 198
  • コメント数: 0
  • カテゴリ: 教養・雑学

 

フェルマーの小定理の証明を思いつきました 有名な証明方法かもしれませんが

 

 

 

フェルマーの小定理とは、apと互いに素なとき、a^(p-1)=1(mod p)になっているという定理です

 

 

 

数学的帰納法を使って証明します

 

 

 

(p-1)Cn=(-1)^n(modp)なので、

 

 

 

(b+1)^(p-1)=b^(p-1)b^(p-2)+b^(p-3)b^(p-4)+……-b+1 (mod p)……①

 

である

 

 これから(b+1)^(p-1)=1 (mod p)(ただしb+10(mod p))を示す

 

(i)

 

b=0のとき

 

1^(p-1)= 1(mod p)

 

なのは明らか

 

 

(ii)

 

b=1のとき

 

2^(p-1)=(1+1)^(p-1)

 

= 1^(p-1)1^(p-2)+ 1^(p-3)-……-1+1←①を参照してください

 

=11+11+…-1+1

 

=1(mod p)

 

よって、2^(p-1)=1(mod p) (ただしp=2の場合は除く)

 

 

 

 

 

 

 

 

 

 

 

 

 

(iii)

 

b=k-1のとき成り立っていればb=kのときも成り立っていること(ただしk±1(mod p))、つまり

 

k^(p-1)=1(mod p)のとき(k+1)^(p-1)=1(mod p)  (ただしk±1(mod p))であることを示す

 

(k+1)^(p-1)=k^(p-1)k^(p-2) k^(p-3)k^(p-4)+……-k1 (mod p)←①を参照して下さい

 

=(k-1)×k^(p-2)(k-1)×k^(p-4)+ (k-1)×k^(p-6)+……+(k-1)×k1

 

=k(k-1)×(k^(p-3)+ k^(p-5)+ k^(p-7)+……+k^2+1)1

 

=k(k-1)×(k^(p-1)-1)/(k^2-1)1

 

=k×(k^(p-1)-1) /(k+1)1(mod p)

 

k^(p-1)=1(mod p)なので、k×(k^(p-1)-1) /(k+1)=0

 

よって、(k+1)^(p-1)=1(mod p)

 

 

 

(i),(ii),(iii)より

 

apと互いに素なとき、a^(p-1)=1(mod p)であることが言える

 

 

公序良俗に反する不適切な投稿を発見された方はこちらよりご報告ください

この投稿にフォローする

コメントをつけるにはログインが必要です。

コメントはまだありません。