次の問題について見ていきます。
(例題)
(1)\(a,b\)を互いに素である自然数とするとき、\(a,2a,3a,4a\)\(・・・,(b-1)a\) をそれぞれ\(b\)で割ったときの余りはすべて異なることを示せ。
(2)\(a\)を自然数、\(p\)を素数とする。\(a,p\)が互いに素であるとき、\(a^{p-1}\)を\(p\)で割ったときの余りは\(1\)であることを示せ。
(解答)
(1)
異なる整数\(m,n\)を、\(1≦m<n<b\) とする。
\(ma\)と\(na\)を\(b\)で割った余りが等しいと仮定すると
\(na-ma=kb\) (\(k\)は整数) と表せる。
\(a(n-m)=kb\) と\(a,b\)が互いに素であることから、\(n-m\)は\(b\)の倍数である。
しかし、\(1≦n-m<b-1\) より、\(n-m\)が\(b\)の倍数とならないので矛盾。
よって、\(b\)で割った余りはすべて異なる。
(2)
\(a,2a,3a・・・,(p-1)a\)は全部で\(p-1\)個であり、さらに\(p\)で割った余りは全部違います。一般的に\(p\)で割った余りは、\(0,1,2・・・,p-1\) (全部で\(p\)個)であり、\(a,p\)が互いに素なので、\(a,2a,3a・・・,(p-1)a\)は\(p\)の倍数ではない、つまり余りが\(0\)になることはありません。
よって、\(a,2a,3a・・・,(p-1)a\) (全部で\(p-1\)個)の数の余りは別々で、\(1,2,3,4・・・,p-1\) (全部で\(p-1\)個) のいずれかとなります。
\(a^{p-1}\)という形をつくるために、\(a,2a,3a・・・,(p-1)a\)の積をとって、今説明したことを利用していきます。
(1)より
\(a,2a,3a・・・,(p-1)a\)・・・① を\(p\)で割った余りはすべて異なる。
また、\(a,p\)が互いに素であることから、①は\(p\)の倍数ではない。
よって、①を\(p\)で割った余りは別々で、\(1,2,3,・・・,p-1\) のいずれかをとる。
ここで、①の積を考えると
\(a×2a×3a×・・・(p-1)a=a^{p-1}(p-1)!\)・・・②
また、\(p\)を法とする合同式より
\(a×2a×3a×・・・(p-1)a\)\(≡1×2×3・・・×(p-1)\)\(≡(p-1)!\) (\(\mathrm{mod}\) \(p\))・・・③
②③より
\(a^{p-1}(p-1)!≡(p-1)!\)・・・④ (\(\mathrm{mod}\) \(p\))
\(p\)は素数なので、\(1,2,3・・・,p-1\) すべてが\(p\)と互いに素である。
よって④の両辺を\((p-1)!\)で割って
\(a^{p-1}≡1\) (\(\mathrm{mod}\) \(p\))
\(a^{p-1}≡1\) (\(\mathrm{mod}\) \(p\))
をフェルマーの小定理(第1形式) とよびます。
数学的帰納法や二項定理を使った別の方法の証明や、第2形式については、数ⅡBで扱います。
以上になります。お疲れさまでした。
ここまで見て頂きありがとうございました。