« オイラーの定理とフェルマーの小定理(合同式) | トップページ | 酔歩(ランダム・ウォーク) »

2006年9月13日 (水)

フェルマーの小定理の別証明

 前記事の"フェルマー(Fermat)の小定理"ですが,"オイラー(Euler)の定理"からそれを証明するのは少し大げさな気がします。

 

 これはもっと簡単で,恐らくよりポピュラーな方法で証明できるので,それも紹介しておきましょう。

 要するに,x,yを任意の整数,pを任意素数とするとき,(x+y)p≡xp+yp (mod p)が成立することさえ証明できれば,任意の整数aに対してap≡a (mod p)が成立することが示せます。

 

 そこで,後はaとpが互いに素ならa≡0 (mod p)ではないので,両辺をaで割ることにより,ap-11 (mod p)が示されるというわけです。

 具体的には,x,y,zを任意の整数,pを任意の素数とすると(x+y+z)p(x+y)p+zp≡xp+yp+zp (mod p)が成立しますから,

 

 整数x,y,zの3つを,さらに4つ,5つ..といくら増やしていってもこうした性質が常に成り立つことになります。

 そこで,もしaが正の整数なら,a=1+1+..+1でありaは1をa個加えたもので,もちろん 1p=1ですから,p1+1+..+1≡a (mod p)が成立するわけです。

 

 また,a=0 ならap≡a (mod p)は自明です。

 

 aが負の整数ならa=-1-1-..-1ですが,素数pは2以外は奇数ですからp≠2なら(-1)p=-1です。

 

 p=2のときも-1≡1 (mod 2)ですから,やはり(-1)2≡-1(mod 2)なので,ap1-1-..-1≡a (mod p)が成立します。

 では,上の証明で前提とした等式:(x+y)p≡xp+yp(mod p)は本当に成立するのでしょうか?

 これの成立は式の左辺を二項展開することで証明することができます。

 

 すなわち,(x+y)p=∑prp-rですが,pはr≠0 のときはp=p(p-1)(p-2)..(p-r+1)/r!です。

 

 右辺の分母のr!の因数はr≠pのときは全てpよりも小さく,分子の素数pとは互いに素ですから,明らかにpはpで割り切れます。

 

 すなわち,p0pp=1であり,1≦r≦p-1ならp≡0 (mod p)ですから,(x+y)p≡xp+yp (mod p)が確かに成立することが示されました。

 しかし,高校の"順列と組み合わせ"で初めて習ったnはnを任意の整数とし,rを1≦r≦nの任意の整数とするとき,本当にいつも整数になるのでしょうか?

 

 確かに,nは組み合わせの数を示すものですから整数になるのは当たり前といえば当たり前ですが,代数的に証明しないと私には何か気持ちが悪いです。

 

 というわけで,これを二重帰納法によって証明してみたいと思います。

 そのために,a,rを任意の整数として(a;r)≡a(a+1)(a+2)..(a+r-1)と定義し,これがr!で割り切れることを帰納法で証明することを考えます。

 r=1のときには(a;r)=(a;1)=aでありr!=1ですから,明らかに(a;r)はr!で割り切れます。

 そこで,r>1とし,第一の帰納法の仮定として,あらゆるaに対して(a;r-1)は(r-1)!で割り切れるとします。

 すると,a=1のときには(a;r)=(1;r)=r!ですから,このときは(a;r)は明らかにr!で割り切れます。

 そこで,第二の帰納法の仮定として,あるaに対しては(a;r)がr!で割り切れるとします。

 このとき,(a+1;r)=(a+1)(a+2)..(a+r-1)(a+r)=a(a+1)(a+2)..(a+r-1)+r(a+1)(a+2)..(a+r-1)=(a;r)+r×(a+1;r-1)となりますから,右辺の第1項も第2項も仮定によってr!で割り切れます。

以上から,任意のaとrに対して(a;r)はr!で割り切れることが証明されました。ここで,n=a+r-1と置けば(a;r)/r!=nですから,結局nが常に整数であることが示されたわけです。

ちなみに,"Eulerーの定理:aφ(m)1 (mod m)"を"Fermatの小定理"から証明することもできます。

 

指針だけを示すと,まずmが素数pのベキ乗であるとき:m=pαのときにEulerの定理が成立することを証明し,一般のmの場合はmを素因数分解すれば証明することができます。

 

ただし,φ(pα)=pα-pα-1,φ(mn)=φ(m)φ(n)などEuler関数φ(m)の性質を使う必要があります。

 

参考文献:松坂和夫著「代数系入門」(岩波書店)

 

http://fphys.nifty.com/(ニフティ「物理フォーラム」サブマネージャー)                                       TOSHI

http://blog.with2.net/link.php?269343(ブログ・ランキングの投票)↑ここをクリックすると投票したことになります。

|

« オイラーの定理とフェルマーの小定理(合同式) | トップページ | 酔歩(ランダム・ウォーク) »

303. 代数学・数論」カテゴリの記事

コメント

 追伸2:kskさん、そのコメントは一つ前の記事につけてもらいたかったですね。そこでは確かに、結論は合っていますが私が間違った論法を使っているのは事実でしたので訂正しておきます。

 ありがとうございました。

    TOSHI

投稿: TOSHI | 2006年9月26日 (火) 08時57分

 追伸、pが素数でない数mならおっしゃるとおり「a≡0 (mod m)でない」からといって合同式の両辺をaで割る割り算はできません。しかしaとmが互いに素ならaで割ってもよいと言い換えることはできますね。

               TOSHI

投稿: TOSHI | 2006年9月26日 (火) 08時53分

 こんにちは、kskさん、TOSHIです。
引き続きコメント頂き恐れ入ります。

「am ≡ an (mod p) であって a ≡ 0 (mod p) でないとき,
 合同式の両辺を a で割っても正しい合同式になるとはかぎらない」

 それはそうなのですがab≡0 (mod p)のときはpが素数ならa≡0かb≡0のどちらかになるのでa≡0でないならb≡0になります。

 つまりabが素数pで割り切れるならばaかbのどちらかがpで割り切れますね。

 だからa≡0つまりaがpで割り切れないならb≡0になります。a^p-a=a{a^(p-1)-1}≡0なのでa≡0でなければa^(p-1)-1≡0 が成り立ちます。

 私の例も失礼でしたがやはりpが素数であるということが必要で素数であればaとpが互いに素というのはaがpで割リきれないという意味の「a≡0ではない」と同値で、pが素数なら「a≡0でない」ときには両辺をaで割ってもかまいませんね。

TOSHI

 

投稿: TOSHI | 2006年9月26日 (火) 08時47分

早速のお返事ありがとうございます.
説明不足ですみません.
私が指摘したかったのは,
「am ≡ an (mod p) であって a ≡ 0 (mod p) でないとき,
 合同式の両辺を a で割っても正しい合同式になるとはかぎらない」
ということです.
例えば,16 ≡ 4 (mod 6) ですが,
両辺を 4 で割ると 4 ≡ 1 (mod 6) となり
正しくない式になってしまいます.
したがって,a ≡ 0 でないという条件だけでは
「両辺を a で割ることによりa^(p-1) ≡ 1 が示される」
ということは言えないのではないかと思います.
前のコメントでは,TOSHI さんの記事のどこを修正すべきかということを考えていたので,
「am ≡ an (mod p) であって a (≠0) と p が互いに素のとき,
 合同式の両辺を a で割っても正しい合同式になる」
といえれば正しい証明になるのではないかということを言いたかったわけです.
説明下手で非常に申し訳ないです.


投稿: ksk | 2006年9月25日 (月) 19時35分

 失礼、例が悪すぎました。

 5≡1(mod4)なのでnが何であろうと5^n≡1 (mod4)は当たり前でしたね。

               TOSHI

投稿: TOSHI | 2006年9月25日 (月) 12時41分

 どもkskさん、コメントありがとうございます。TOSHIです。

>a と p が互いに素ではなくても
フェルマーの小定理が成り立つことになってしまいます.

あ、「フェルマーの小定理」は十分条件であって必要十分条件ではないので「a と p が互いに素ではなくても別にa^(p-1) ≡ 1 (mod p)が成り立ってもいい」のですよ。

 もっとも(a,p)という最大公約数は、pが素数なので約数がpか1かのどちらかですから「aとpが互いに素」というのと「a ≡ 0 (mod p) ではないこと」は同値なのですが。。。。

pが素数でない、たとえばp=4でaが5の場合も5^(p-1)=5^3=125≡1(mod4)です。これは5^4≡5から「5≡0(mod4)ではない」ことから5で割ることにより得られます。


TOSHI

投稿: TOSHI | 2006年9月25日 (月) 12時35分

楽しく拝見させていただきました.
ただ,a^p ≡ a (mod p) のときに
a ≡ 0 (mod p) ではないからといって,
両辺を a で割って a^(p-1) ≡ 1 (mod p)
とは言えないと思います.
「a ≡ 0 (mod p) ではないこと」と
「a と p が互いに素であること」は同値でないので,
上の割り算が自由にできてしまうと,
a と p が互いに素ではなくても
フェルマーの小定理が成り立つことになってしまいます.
したがって,
「互いに素の場合のみ両辺をそのまま割ることができる」
ようなことを言わなければならないはずです.

投稿: ksk | 2006年9月25日 (月) 11時37分

コメントを書く



(ウェブ上には掲載しません)




トラックバック

この記事のトラックバックURL:
http://app.f.cocolog-nifty.com/t/trackback/71281/3422864

この記事へのトラックバック一覧です: フェルマーの小定理の別証明:

« オイラーの定理とフェルマーの小定理(合同式) | トップページ | 酔歩(ランダム・ウォーク) »