オイラーのφ関数

MIPOの算数・数学コラムで，2024年阪大理系前期数学の問題が取り上げられていた。鈴木貫太郎のYouTubeで大学入試問題をながめていたので，甘く見ていたら，かなり難しくてちょっと手が出なかった。面白そうな整数論の問題は，オイラーのφ関数がストレートに取り上げられていた。以下ではすべて自然数 N = {1,2,...∞}の範囲に限定して考えることにする。

n∈Nに対して，集合A(n)={1,2,…n}を考える。このとき，φ(n)は，この集合A(n)におけるnと互いに素な数の個数を与える。さあ，ここからが苦難の道の始まりだ。最近はアルジャーノンの下り坂を急降下中なので，言葉の定義にいちいち引っかかってころぶのである。

・約数：自然数 n を自然数m (≦ n)で割ったときの余りが0であれば，mはnの約数である。

　例：2は6の約数，1はnの約数，nはnの約数

・互いに素：2つの自然数 m,n の共通の約数が1だけのとき，mとnは互いに素である。

　例：2と3は互いに素である，nと1は互いに素である，nとnは互いに素でない。

例：n=6のとき，A(6)={1,2,3,4,5,6}を考える。2の倍数の集合Pは{2,4,6}, 3の倍数の集合Qは{3,6}, 

6の倍数の集合はP∩Q={6}は，6と互いに素な数の集合はA-P∪Q={1,5}で, その要素数はφ(6)=2

オイラーのφ関数（トーシエント関数）φ(n)は，A(n)においてnと互いに素な数がなす部分集合B(n)の要素数を表す。A(n)-B(n) は nの約数の集合から{1}を除いた集合P∪Q∪Rである。

阪大の問題は，p,q,r が素数，a,b,c が自然数として n=p^a q^b r^cに対するφ(n)を求めるものである。とりあえず，A(n)における p,q,rの倍数の数をカウントすればよい。

図：φ(n) = n(B(n))=n(A(n)-P∪Q∪R)   の図

n= p^a q^b r^c の場合，n= p^(a-1) q^(b-1) r^(c-1) p q r として，φ(n) = p^(a-1) q^(b-1) r^(c-1) φ(p q r )となる。また，φ(p q r) = (p-1)(q-1)(r-1) となるので，φ(n) =p^(a-1) q^(b-1) r^(c-1) (p-1)(q-1)(r-1) で与えられる。