オイラーは、数の性質(特に素数の分布)を 調査し続けました。 彼の扱った重要な関数の1つに φ(ファイ)関数があります。 φ関数は、数字の分割性を示します。 例えば Nという数が与えられた時、 φ関数では N 以下の数のうち、 Nと公約数を持たない数の個数が解となります。 例えば、8のφを見てみましょう。 まず1から8までの数を並べます。 そして、2以上の整数で8と公約数のないものを数えます。 そして、2以上の整数で8と公約数のないものを数えます。 たとえば6は数えることができません。 8と6は共に2で割ることができるからです。 一方、1、3、5、7は数えることができます。 これらは、8との公約数を1以外で持たないからです。 よって、 φ(8)=4 です。 φ関数の面白いところは、 ある特別な場合に 簡単に計算ができることです。 このグラフは、 1から1000までの整数の φ(N)の値を図にしたものです。 さて、なにか予測可能なパターンに気づくでしょうか? 直線に見える部分が、全て素数を表しているのです。 直線に見える部分が、全て素数を表しているのです。 素数は1以外に公約数を持たないので、 どんな素数(P)でも φ関数の値は(P-1)となります。 φ(7)を計算してみましょう。 7は素数なので、7以外の数は数えることができます。 7以外は公約数がないですからね。 φ(7)=6になります。 だから、もし素数である21377のφを求めよ といわれたら、 ただそこから1をひくだけで答えが出ます。 つまり、21376 です。 ただそこから1をひくだけで答えが出ます。 つまり、21376 です。 どんな素数でもφを計算することは簡単です。 他にも、応用可能な面白い性質があります。 それはφ関数はかけ算もできるということです。 つまりは、φ(A×B)=φ(A)×φ(B)という関係です。 もし、ある数Nが2つの素数(P1,P2) の積で あらわされることが分かっている時、 もし、ある数Nが2つの素数(P1,P2) の積で あらわされることが分かっている時、 φ(N)は、それぞれのφのかけ算と同じになります。 φ(N)は、それぞれのφのかけ算と同じになります。 つまり、(P1−1)×(P2−1)です。