2024年4月18日木曜日

オイラーのφ関数

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}を除いた集合PQRである。

阪大の問題は,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)-PQR)   の図

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) で与えられる。

0 件のコメント:

コメントを投稿