オイラー関数を計算する
ある正の整数nに対して，nより小さい正の整数の中で互いに素なものの個数をオイラー関数といいます。オイラー関数はファイ（$\varphi $）関数といい、$\varphi (n)$で表現します。ここではPythonを使って、オイラー関数を計算します。
定義通りにオイラー関数を計算する
nとある数が互いに素ということは最小公倍数が1ということです。そこで別に作ったgcd関数を使い計算します。最大公約数は2つの正の整数の共通の約数で、gcdはgreatest common divisorの略です。
最大公約数を計算する
2つの変数aとbの最大公約数を計算します。ここでは、ユークリッドの互除法を使って計算します。
ユークリッドの互除法による最大公約数を求める関数
- def gcd(a, b):
- while b:
- a, b = b, a % b
- return a
- print(gcd(12,18))
- print(gcd(15,12))
6 3
上記の通り2つの引数の大小を問わず、正しく最大公約数を計算することができます。
最小公倍数が1である数を計算することによりオイラー関数を計算
オイラー関数を計算するphiという関数を作成します。ここでは次の変数を使用します。
- num
- 関数の引数で、オイラー関数を求めたい正の整数
- cnt
- 正の整数num以下の互いに素の数を数える。最終的にオイラー関数の値になる。
- i
- num以下の正の整数で、1つずつnumと互いに素かどうかを調べるための変数
gcd関数を使ってオイラーの関数を計算する
- def phi(num):
- cnt=0
- for i in range (1,num+1):
- if gcd(num,i)==1:
- cnt+=1
- return cnt
- phi(18)
6
3. 変数iを1から引数numまでループし、gcd関数を使い最大公約数が1である場合、互いに素となる整数として数えています。ほとんどの場合3.ではnum（引数-１）まで計算すれば問題ありませんが、$\varphi(1)=1$とするため、num+1としてnumまで計算します。
4.～5. 2.で初期化したcntを使い、iがgcd=1（互いに素）の場合、cntを1つ増やします。
8. 18より小さく、18と互いに素の正の整数は1,5,7,11,13,17の6つなので、正しく計算されたことがわかります。
オイラー関数の計算の基礎となる互いに素となる数をリストで返す
前節の計算と同じ考え方で、互いに素となる数をリストで返すphi_2関数を作成します。ここでは、計算結果を格納するため、リストtotientを使います。オイラー関数は英語でEuler's totient functionといいます。totientとは見慣れぬ言葉ですが、「互いに素」を意味し、totとはラテン語でたくさんを指します。
ある整数以下の数で互いに素なものをリストで返す
- def phi_2(num):
- totient =[]
- for i in range (1,num+1):
- if gcd(num,i)==1:
- totient.append(i)
- return totient
- print(phi_2(18))
[1, 5, 7, 11, 13, 17]
5. 前項のプログラムで、cntを加算する代わりに、リストtotientに互いに素の数を追加します。
8. 18と互いに素の数は1, 5, 7, 11, 13, 17となり、計算結果が正しいことがわかります。
オイラー関数の性質
オイラー関数には、面白い性質がたくさんあります。この性質を使い、最終的にオイラー関数を計算する別の方法を考えます。
素数のk乗に対するオイラー関数
素数pに対してオイラー関数を適用するとp-1になります。さらに、$n=p^k$の場合，$\varphi(p^k)$は$p^k$以下の正の整数でpの倍数でないものの数なので $\varphi(n)=p^k\left(1-\dfrac{1}{p}\right)=p^k-p^{k-1}$ となります。このことをphi関数で計算することで正しいことを確認します。
素数のk乗に対するオイラー関数
- p=7
- print('乗数 φ(p) p**k(1-1/p)')
- for i in range(1,10):
- print(f'{i} {phi(p**i):>10d} {p**i-p**(i-1):>10d}')
乗数 φ(p) p**k(1-1/p) 1 6 6 2 42 42 3 294 294 4 2058 2058 5 14406 14406 6 100842 100842 7 705894 705894 8 4941258 4941258 9 34588806 34588806
上記のことから、計算が正しいことが確認できました。
オイラ―関数の積に関するルール
正の整数m,nが互いに素のとき、$\varphi(mn)=\varphi(m) \varphi(n) $となります。これを証明するのは大変なのでここでは、実際に数値を当てはめて確認するにとどめます。
オイラー関数の掛け算
- print (' i j φ(i) φ(j) φ(i)×φ(j) φ(i×j) ')
- for i in range(2,10):
- for j in range(2,10):
- if gcd(i,j)==1:
- print(f'{i:>4d} {j:>4d} {phi(i):>4d} {phi(j):>4d} {phi(i)*phi(j):>8d} {phi(i*j):>10d}')
i j φ(i) φ(j) φ(i)×φ(j) φ(i×j) 2 3 1 2 2 2 2 5 1 4 4 4 3 2 2 1 2 2 3 4 2 2 4 4 3 5 2 4 8 8 4 3 2 2 4 4 4 5 2 4 8 8 5 2 4 1 4 4 5 3 4 2 8 8 5 4 4 2 8 8 5 6 4 2 8 8 6 5 2 4 8 8
上記のことから、計算が正しいことが確認できました。
もう一つのオイラー関数の計算の方法
前節の2つの定理を応用することにより、素因数分解の結果を使いオイラー関数を計算することができます。正の整数nの素因数分解を、$n=p_1^{k_1}p_2^{k_2}\cdots p_m^{k_m}$ とすると
$\varphi(n)=(p_1^{k_1}-p_1^{k_1-1})(p_2^{k_2}-p_2^{k_2-1})\cdots(p_m^{k_m}-p_m^{k_m-1})$$\displaystyle = p_1^{k_1}\left(1-\frac{1}{p_1}\right)p_2^{k_2}\left(1-\frac{1}{p_2}\right)\cdots p_m^{k_m}\left(1-\frac{1}{p_m}\right)$ $\displaystyle=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_m}\right)$
となります。
例えば、$p_m^{k_m}$に対しては、前項、素数のk乗に対するオイラー関数の考え方により$\varphi(p_m^{k_m})=p_m^{k_m}\left(1-\dfrac{1}{p_m}\right)$となります。また、$p_1^{k_1}、p_2^{k_2}\cdots、 p_m^{k_m}$は互いに素なので、オイラ―関数の積に関するルール$\varphi(mn)=\varphi(m) \varphi(n) $を使うことができます。これらのことからオイラー関数の公式をあてはめることにより計算することが可能になります。
素因数分解をする
素因数分解をするprime_f関数を作成します。
素因数分解をする関数
- def prime_f(num):
- divisors={}
- i=2
- while(i <= num):
- k=0
- while(num % i == 0):
- k+=1
- num //= i
- if k != 0:
- divisors[i]=k
- i += 1
- return divisors
- print(prime_f(18))
{2: 1, 3: 2}
結果は、$2^3×3^2$を辞書形式で計算されます。
素因数分解した結果を使いオイラー関数を計算する
前のプログラムで作成した素因数分解の結果prime_fに対して公式を使い、オイラー関数を計算します。ここでは、次の辞書を使います。
- d
- オイラー関数を計算したい正の整数の素因数分解の結果を格納します。
- d.key
- 素因数分解は素数（$p_m$）とそのべき乗（$k_m$）の積で計算されますが、辞書dのkeyは素数（$p_m$）の部分を表します。
素因数分解の結果からオイラー関数を計算する
- from decimal import Decimal
- num = 18
- d = prime_f(num)
- for key in d.keys():
- num *= 1-1/Decimal(str(key))
- int(num)
6