ある整数の約数に対するオイラー関数の和がある整数になる

Pythonでオイラー関数を計算する

オイラー関数は、ある整数に対し、その整数より小さくかつ互いに素（最大公約数=1)となる整数の個数を計算します。オイラー関数の前提として、Pythonでは次の通り最大公約数を計算することができます。

#最大公約数を計算する
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

print(gcd(12,18))
print(gcd(15,12))

#6
#3

続いて、最大公約数を計算するgcd関数を使い、オイラー関数を計算します。

#オイラー関数を計算する
def phi(num):
    cnt=0
    for i in range (1,num+1):
        if gcd(num,i)==1:
            cnt+=1
    return cnt
    
print(phi(18))
print(phi(5))
print(phi(1))

#6
#4
#1

オイラー関数は、ギリシア文字で$\varphi$（ファイ）であらわすので、関数名をphiとします。

ある正整数の約数についてオイラー関数を合計すると、その整数になる

ある正整数について約数を計算し、さらにその約数に対するオイラー関数を計算します。これを全て合計すると、もとの正整数に戻ります。とても興味が惹かれる定理なので、実際に試してみます。

はじめに、約数を計算する関数を作成します。引数でnumを指定すると、その約数をリストで返します。

#約数の一覧をリストで返す関数
def divisors_list(num):
    divisors = []
    for i in range(1, num+1):
        if num % i == 0:
            divisors.append(i)
    return divisors

divisors_list(36)

#[1, 2, 3, 4, 6, 9, 12, 18, 36]

この関数を使い、検証してみます。divisors_listをつかい約数のリストを作り、このリストの各要素についてphi関数でオイラー関数を計算し、足しこんでいきます。

# 約数に対するオイラー関数の値の和
print(' n   phi')    
for i in range(2,10):
    d_l = divisors_list(i)
    total=0
    for divisor in d_l:
        total+=phi(divisor)
    print(f'{i:2d}   {total:2d}')    

 n   phi
 2    2
 3    3
 4    4
 5    5
 6    6
 7    7
 8    8
 9    9

2から9までの整数につき、正しく計算できていることがわかりました。

正整数の約数についてオイラー関数を合計が等しい理由

前節のような不思議なことがおこる理由を直感的に確認してみます。まず、整数18を例にそれ以下の正整数を18との最大公約数で分類し、辞書形式で表現します。

# ある数以下の整数を最大公約数で分類
num=18
divisor = {}
for i in range(1, num+1):
    g = gcd(i, num)
    if g in divisor:
        divisor[g].append(i)
    else:
        divisor[g] = [i]
print(divisor)

{1: [1, 5, 7, 11, 13, 17], 2: [2, 4, 8, 10, 14, 16], 3: [3, 15], 6: [6, 12], 9: [9], 18: [18]}

最大公約数が1になる[1, 5, 7, 11, 13, 17]は、その定義から18と互になります。

# 約数のオイラー関数の和が元の数に戻る
complement = {}
irreducible = {}
for i in divisor.keys():
    irreducible[i] = list(map(lambda x: int(x/i), divisor[i]))
    j = int(num/i)
    complement[j] = irreducible[i]
    
print(irreducible)
print(complement)

{1: [1, 5, 7, 11, 13, 17], 2: [1, 2, 4, 5, 7, 8], 3: [1, 5], 6: [1, 2], 9: [1], 18: [1]}
{18: [1, 5, 7, 11, 13, 17], 9: [1, 2, 4, 5, 7, 8], 6: [1, 5], 3: [1, 2], 2: [1], 1: [1]}

辞書形式のデータの各要素の対し、分類された整数を最大公約数で割ります。たとえば、最大公約数が2の組は[2, 4, 8, 10, 14, 16]となり、その約数には2が含まれるので当然に割り切れます。この結果はirreducibleという辞書に代入します。このような割り算は、簡約するといい、簡約されている状態を既約（irreducibed）といいます。

次に、辞書irreducibeedに対し、最大公約数の部分を18を割った時の相手方（補約数）に置き換え、complementという辞書に代入します。補約数とは18の場合、１と18、2と9、3と6のように書けると18になるペアをいいます。ここで、2と9のペアを確認します。結果的には18との最大公約数が2の組である[2, 4, 8, 10, 14, 16]の組合せについて簡約し、9と[1,2,4,5,7,8]の組になります。この要素の整数は2の補約数9とは互いに素になるはずです。

このことから、例えば18以下の整数は最大公約数1,2,3,6,9,18のいずれかに分類され、その集まりは最大公約数の補約数と互に素になります。このため、ある整数の約数に対してオイラー関数を計算し、足しこんでいくとその合計は元の整数18になるわけです。