合同の証明について

質問

pを素数とします。
１≦ｋ≦ｐ－２なら、a^kがpを法として１と
合同でない自然数aが存在することが分かって
います。
このとき、｛１，２，・・・ｐ－１｝と
｛ai |１≦i≦ｐ－１｝はmodpで集合として
一致することを示したいのですが、具体的な
証明方法は分かりません。
数字を入れていくつか確かめてみたのですが、
これをどう一般的に証明するのかが分かりま
せん。
回答の方、よろしくお願い致します。

回答No.1

yoikagari · ベストアンサー

背理法を用います
もし、｛a*i |1≦i≦p-1｝はmod　pで、｛1，2，・・・、p-1｝と一致しないと仮定して矛盾を導くのです。

もし、｛a*i |1≦i≦p-1｝がmod　pでp-2個以下の値しかとらないと仮定します。…※

すると、｛1，2，・・・、p-1｝はp-1個の値がありますので、あるuとv(uとvは1≦u＜v≦p-1となる自然数)が存在して、a*u≡a*v　(mod　p)となることがわかります。…※
(もし、※のような自然数uとvが存在しなければ、a、2*a、…、a*(p-1)はmod　pで異なる値になるから、、｛a*i |1≦i≦p-1｝がmod　pでp-1個の値をとることになります)

aとpは互いに素だから、u≡v　(mod　p)となることがわかります。

ところが、1≦u＜v≦p-1だから、u≡v　(mod　p)は
0＜v-u＜p-1なる整数v-uがpで割り切れることを意味し、不合理。

したがって、※の仮定は誤りで、｛a*i |1≦i≦p-1｝がmod　pでp-1個の値を取ることが分かります。

したがって、
｛a*i |1≦i≦p-1｝がmod　pで{1,2,…p-1}に含まれることを考慮すると、｛a*i |1≦i≦p-1｝がmod　pで{1,2,…p-1}に一致することが示されます。

お礼

ありがとうございました。まさか、背理法を使うなんて思っていませんでした。また、aとpが互いに素だということにきづかなかったです。よくわかりました。本当にありがとうございました。