3.Möbius関数、Euler関数


まず、σ(n)(nの約数の和)のプログラムを再掲する。

10   fnSigma(N)
20   local P,S,W
30   S=1
40   while N>1
50     W=1:P=prmdiv(N)
60     W=W*P+1:N=N\P:if N@P=0 then 60
70     S=S*W
80   wend
90   return(S)

以下の Möbius 関数、Euler 関数についても、σ(n) 同様、
nの素因数分解された形についての公式となっており、
σ(n)を求めるときに使った、素因数を順次見つけながら計算していく
というアルゴリズムが役立つ。

Möbius関数 μ(n)

Möbius関数μ(n) の定義は以下のとおりである。
(「メビウス」と読む。あの「メビウスの輪」のメビウスである。)

アルゴリズムとしては、

とすればよい。プログラムは以下のとおり。

10   fnMobius(N)
20   local P,W
30   W=1
40   while N>1
50     P=prmdiv(N):if N@(P^2)=0 then return(0)
60     W=W*(-1):N=N\P
70   wend
80   return(W)

UBASICでは、moeb(n) という組み込み関数になっている。

Euler関数 φ(n)

nに対し、n以下でnと互いに素になる数の個数を与える関数を、Euler関数と呼び、φ(n)で表す。
(「オイラー」と読む。ちなみに、あらゆるジャンルで「オイラー」という名が冠せられた
定理・法則・公式・定数等があるが、全て同一人物によるものである)。
Euler関数は、以下の公式により与えられる。

自然数nが、

n=p1e1・p2e2・……・pkek

と素因数分解されるとき、

φ(n)=n(1−1/p1)(1−1/p2)・……・(1−1/pk)

プログラムは以下のとおり。

10   fnEuler(N)
20   local P,W
30   W=N
40   while N>1
50     P=prmdiv(N):W=W\P*(P-1):' w=w*(1-1/p)
60     repeat N=N\P until N@P>0
70   wend
80   return(W)

UBASICでは、eul(n) という組み込み関数になっている。


さて、100以下の数について、

の値を見てみる。ついでに、

の値も示す。

nσ(n)φ(n)μ(n)(σ(n)+φ(n)) mod n
231-10
342-10
47201
564-10
612212
786-10
815403
913601
1018412
111210-10
1228408
131412-10
1424612
1524812
1631807
171816-10
1839609
192018-10
20428010
21321212
22361012
232422-10
24608020
25312001
26421212
27401804
285612012
293028-10
30728-120
313230-10
326316015
33482012
34541612
35482412
369112031
373836-10
38601812
39562412
409016026
414240-10
429612-124
434442-10
448420016
457824012
46722212
474846-10
4812416044
49574201
509320013
51723212
529824018
535452-10
5412018030
55724012
5612024032
57803612
58902812
596058-10
601681604
616260-10
62963012
6310436014
6412732031
65844812
6614420-132
676866-10
6812632022
69964412
7014424-128
717270-10
721952403
737472-10
741143612
7512440014
7614036024
77966012
7816824-136
798078-10
8018632058
8112154013
821264012
838482-10
8422424080
851086412
861324212
871205612
8818040044
899088-10
9023424078
911127212
9216844028
931286012
941444612
951207212
9625232092
979896-10
9817142017
9915660018
10021740057

この表を見ていると、いろいろなことに気付く。

  1. nが素数のとき、μ(n)=−1である。
    このとき σ(n)+φ(n)≡0 (mod n) となる(これは証明できる)。
    では、σ(n)+φ(n)≡0 (mod n) のとき、nは必ず素数となるか?

  2. μ(n)=0かつ σ(n)+φ(n)≡1 (mod n) となるのは、
    n=i2、iが素数のときに限る(これも証明できそう)。

  3. σ(n)+φ(n)≡2 (mod n) のとき、μ(n)=1。
    では、μ(n)=1のとき、必ずσ(n)+φ(n)≡2 (mod n) となるか?

答えを云ってしまうと、

1.はならない。最小の反例は312。
3.もならない。最小の反例は210。


この章の目次

E-mail : kc2h-msm@asahi-net.or.jp
三島 久典