【 問 題 】

　 P を素数とし、それ未満の１以上の自然数を a とする。
　 a，2a，3a，・・・・，(P−1)a　を P で割った余りは全て異なることを証明せよ。

【 解 答 】

　 仮定命題 ：　a，2a，3a，・・・・，(P−1)a　を P で割った余りはどれか等しい。

　 すると、次の式をみたす m と n のペアが存在することになる。
　　　　1 ≦ m ＜ n ≦ P−1　・・・ �@
　　　　m と n は自然数
　　　　am と an を P で割った余りが等しい。　・・・ �A
　 P と a とは互いに素であるので、�@ と �A より m ＝ n となる。
　 これは m ＜ n　に矛盾する。
　 したがって、 仮定命題は偽である。
　 よって、 a，2a，3a，・・・・，(P−1)a　を P で割った余りは全て異なる。

【 解 説 】

　 この命題が真であることが証明できたので、a，2a，3a，・・・・，(P−1)a　までをすべて掛け合わせた数 を P で割った余りが (P−1)! を P で割った余りに等しくなるなることを用いて「 フェルマーの小定理 」を導くことができます。
　　　 aⁿ⁻¹(P−1)! ≡ (P−1)!　( mod P )

　　　 参考：　大学生のための数学 ＞ 数理論 ＞ フェルマーの小定理