小説 φは壊れたね （その2）

φ　関数　空集合　
以前の同じ小説の投稿の第2弾です。
----
「φっていうのは、何に使う記号ですか？」鵜飼は西之園と国枝を見てきいた。
「決まっていません」西之園が答える。「よく使うというと、関数の名前かしら」
「空集合」国枝が珍しく口をきいた。
----
　よく使うということはないですが、φ関数というものがあります。nを正の整数としてφ(n)は、n以下の整数のうちnと互いに素な（1以外に公約数を持たない）ものの個数を表します。例えば、4以下の正の整数で4と互いに素なものは1と3の2個なので
φ(4)=2
となります。n=12なら、12以下で12と互いに素なものは1と5と7と11の4個なので
φ(12)=4
となります。nが素数pのときは、1からp-1までのすべてがpと互いに素なので
φ(p)=p−1
となります。
　素数も含めて正の整数すべての場合でφ(n)を求める式は少し難しいですが、分かりやすい式はこちらにあります。簡単に言えば、nを素因数分解したときの素因数をp(1)、p(2)、…p(k)としたとき、nと(1-1/p(i))をすべて掛け算したものになります。例えば、4=2^2なのでp(1)=2だから、
φ(4)=4(1-1/2)=2
となります。n=12なら、12=2^2*3なのでp(1)=2、p(2)=3だから、
φ(12)=12(1-1/2)(1-1/3)=4
となり、上の結果と一致します。これなら大きな数でも求められますね。例えば、n=480のとき、480以下の整数のうち480と互いに素なものをすべて数えるのは大変ですが、この式を使うと、480=2^5*3*5なので、
φ(480)=480(1-1/2)(1-1/3)(1-1/5)=128
と容易に求められます。