数理論 へ戻る「 素数
と 正の整数 
がある。 それらの最大公約数が １ であるならば、 
は必ず で割り切れる。」 というのが、 フェルマーの小定理ですが、 オイラーは、 それを拡張することに成功しました。※ 参考： 数理論 ＞ フェルマーの小定理
ある正の整数 
よりも小さくて、 かつ、 との最大公約数が １ である正の整数の数（かず）を 
で表すとき、 との最大公約数が １ である任意の正の整数 について、 
は必ず で割り切れる。
よりも小さくて、 かつ、 との最大公約数が １ である正の整数の数（かず）を で表すとき、 との最大公約数が １ である任意の正の整数 について、 は必ず で割り切れる。これがオイラーの定理です。 なお、 この
は、 オイラー関数と言われています。 彼は、 が素数のときは、 必ず 
になることに注目したのです。 もし 
ならば、 ７ よりも小さくて、 かつ、 ７ との最大公約数が １ である正の整数は、 １， ２， ３， ４， ５， ６ ですから、 
となりますものね。オイラーの定理を確かめるために、 十進BASIC でプログラムを作ってみました。
ちなみに、 ある正の整数
よりも小さくて、 かつ、 との最大公約数が １ である正の整数を小さい順に表示するプログラムは、 次のようになります。オイラーの定理から、 さらに次の定理を導くことができます。
-
２つの異なる素数 ｐ と ｑ をかけた数 Ｎ がある。
Ｎ 未満の自然数 ａ がある。
ａ の ( ｐ−１ )( ｑ−１ ) ＋ １ 乗 を Ｎ で割った余りは ａ である。
JavaScript のプログラムで確かめてみましょう。
プログラムの内容 ：
【 問 題 １ 】
-
２つの異なる素数 ｐ と ｑ がある。 Ｎ ＝ ｐｑ である。
１ 〜 Ｎ までの自然数で Ｎ と互いに素の自然数の数を求めよ。
-
１ 〜 Ｎ までの自然数で 明らかに Ｎ と互いに素でないのは、 Ｎ の １ 個。
それ以外に Ｎ と互いに素でないのは、
ｐ， ２ｐ， ３ｐ， ・ ・ ・ ・ ， （ ｑ − １ ）ｐ の （ ｑ − １ ） 個 と、
ｑ， ２ｑ， ３ｑ， ・ ・ ・ ・ ， （ ｐ − １ ）ｑ の （ ｐ − １ ） 個 で、
その他には存在しない。
したがって、 答えは、
Ｎ − １ − （ ｑ − １ ） − （ ｐ − １ ）
＝→ ｐｑ − ｐ − ｑ ＋ １
＝→ ( ｐ − １ ) ( ｑ − １ )
-
ｎ で割ると １ 余る自然数 ｍ がある。 この数に ｎ より小さな自然数 ｋ をかけた数は ｎ で割ると ｋ 余ることを示せ。
-
ｍ ＝ ａｎ ＋ １ と置くと、 ｋｍ ＝ ａｋｎ ＋ ｋ
ｋ ＜ ｎ より、 ｋｍ は ｎ で割ると ｋ 余ることが解る。