フエルマーの小定理の証明について

質問

ｐを素数としａがｐと互いに素のときａの（ｐ－１）乗≡１（ｍｏｄｐ
　が成り立つ　その証明で　ａ，２ａ，．（ｐ－１）ａをｐで割った余りはすべて異なる、なぜならもし１≦ｉ≦ｊ≦ｐ－１になるｉ，ｊに対してｉａ≡ｊａ（ｍｏｄｐ）となれば、（ｊ－ｉ）ａ≡０（ｍｏｄｐ）
となり、ａとｐが互いに素であることからｊ－ｉがｐの倍数となるので
ｐが素数であることに矛盾する。ｐがなにかの倍数なら素数であること
に矛盾するように感じるがｊ－ｉがｐの倍数だからというところが解りません。これよりａ，２ａ．．（ｐ－１）ａをそれぞれｐで割った余りは、１，２、．．，　　ｐ－１の並べ換えになっている。ここもよく理解
できません。よろしくお願いします

回答No.8

yoikagari · ベストアンサー

やっはり「aとpが互いに素であることからj-iがpの倍数となるので」のくだりまでは
問題ないですが、「pが素数であることと矛盾する」というのはおかしいです。
どこをどう解釈しても、「pが素数であることと矛盾する」というのはおかしいですね。
「1≦i≦j≦p-1」を用いると「j=i」なら示せるけど。

「1≦i≦j≦p-1」ならば「j=i」となる事の証明
証明
1≦i≦j≦p-1だから0≦j-i≦p-2だからj-iは0以上でp-2以下の整数になります。
ところが0以上の整数でpの倍数となるのは、0,p,2p,3p,…と0あるいはp以上の
整数に限られます。
したがって、j-i=0すなわち、j=i
証明終わり

老婆心ながら、一言
整数論の勉強には定評ある本を使ってくださいね(高木貞治著の初等整数論講義など)。
ネットの掲示板の回答はいい加減なものが多すぎますからね。

お礼

大変参考になりました。定評のある本を使いたいと思います。

回答No.7

koko_u_u

>すいません。１１とか１０をどのようにするのでしょうか。

p = 11 として、証明中で行っていることを実際にノートに書き出しましょう。という意味です。

お礼

意味がわかりやってみました。ありがとうございました。

回答No.6

muturajcp

訂正します。
f:{k}_{0≦k≦p-1}→{k}_{0≦k≦p-1},f(k)=mod(ka,p)=(kaをpで割った余り)とする
0≦i≦j≦p-1
f(i)=f(j)ならば
ia≡ja(modp)
(j-i)a≡0(modp)
ならば
(j-i)a=pn となる n　が存在する
左辺を素因数分解すると、その中に素数　p　が存在するから
(j-i)≡0(modp)　または a≡0(modp)　のどちらかが成り立つ
ところが　a と　p　は互いに素だから　a≡0(modp)　ではないから
(j-i)≡0(modp)　が成り立つから
j-iがpの倍数となる
0≦j-i<p だから
j-i=0
j=i
f　は単射だから　fは全単射で、置換(並べ替え)写像となる

お礼

丁寧に解説していただいて大変参考になりました。ありがとうございます。

回答No.5

yoikagari

証明内容自体全然違いますね
「ａ，２ａ，．（ｐ－１）ａをｐで割った余りはすべて異なる、なぜならもし１≦ｉ≦ｊ≦ｐ－１になるｉ，ｊに対してｉａ≡ｊａ（ｍｏｄｐ）となれば、（j-i)ａ≡０（ｍｏｄｐ）
となり、ａとｐが互いに素であることからj-iがｐの倍数となるので
j-iがpで割り切れないことに矛盾する。」じゃないんですか？

pが素数であるので、pが何かの倍数というのは「全くありえない」ですね。
残念ながらあなたは素数の定義を、全く理解していないようです。
フェルマーの小定理の証明の前に、素数の定義や互いに素の定義など、
もっと基本的なことを勉強することを強く勧めます。

素数
http://ja.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0

互いに素
http://ja.wikipedia.org/wiki/%E4%BA%92%E3%81%84%E3%81%AB%E7%B4%A0

補足

説明ありがとうございます。証明はあるテキストを写したものです。ひょっとしてテキストの証明が間違っているのかともおもいます。ｐが素数であることに矛盾するからとあったのですが、自分としては矛盾はまったく無いと思います。教えていただいたｊ－ｉがｐで割り切れないのはなぜでしょうか。よろしくおねがいします。

回答No.4

koko_u_u

全単射だけで十分だと思いますよ。
位数 p-1 の元があるかどうかはまた別問題ということで。

お礼

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

回答No.3

alice_44

a 倍することが｛ 1,2,3,…,p-1 ｝上の全単射
であることを示しても、それだけでは、
写像 x→xa が、
0→0,
1→2,
2→1,
3→…
のような状態でないことまでは言えない。

フェルマーの定理では、
｛ 1,2,3,…,p-1 ｝が x→xa の
ひとつながりの軌道になることが重要なのだから、
全単射だけでは十分でない。

オーソドックスに、数列 a,a~2,a~3,a~4,… の
有限性と周期性から攻めたほうが確実なのでは？

お礼

解説ありがとうございました。参考にさせていただいて勉強します。

回答No.2

muturajcp

f:{k}_{1≦k≦p-1}→{k}_{1≦k≦p-1},f(k)=mod(ka,p)=(kaをpで割った余り)とする
1≦i≦j≦p-1
f(i)=f(j)ならば
ia≡ja(modp)
(j-i)a≡0(modp)
ならば
(j-i)a=pn となる n　が存在する
左辺を素因数分解すると、その中に素数　p　が存在するから
(j-i)≡0(modp)　または a≡0(modp)　のどちらかが成り立つ
ところが　a と　p　は互いに素だから　a≡0(modp)　ではないから
(j-i)≡0(modp)　が成り立つから
j-iがpの倍数となる
ゆえに　j-i=0
j=i
f　は単射だから　fは全単射で、置換(並べ替え)写像となる

お礼

参考になりました。ありがとうございます。

回答No.1

koko_u_u

>ａ，２ａ．．（ｐ－１）ａをそれぞれｐで割った余りは、
>１，２、．．，　　ｐ－１の並べ換えになっている。
>ここもよく理解できません。

具体的な素数(例えば11)について試してみれば理解できるかも。
あるいは合成数(例えば10)についても同じことを試しましょう。

補足

すいません。１１とか１０をどのようにするのでしょうか。ひとつだけでも例を教えてもらえたらありがたいです。