まず、σ(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) の定義は以下のとおりである。
(「メビウス」と読む。あの「メビウスの輪」のメビウスである。)
アルゴリズムとしては、
とすればよい。プログラムは以下のとおり。
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) という組み込み関数になっている。
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 |
---|---|---|---|---|
2 | 3 | 1 | -1 | 0 |
3 | 4 | 2 | -1 | 0 |
4 | 7 | 2 | 0 | 1 |
5 | 6 | 4 | -1 | 0 |
6 | 12 | 2 | 1 | 2 |
7 | 8 | 6 | -1 | 0 |
8 | 15 | 4 | 0 | 3 |
9 | 13 | 6 | 0 | 1 |
10 | 18 | 4 | 1 | 2 |
11 | 12 | 10 | -1 | 0 |
12 | 28 | 4 | 0 | 8 |
13 | 14 | 12 | -1 | 0 |
14 | 24 | 6 | 1 | 2 |
15 | 24 | 8 | 1 | 2 |
16 | 31 | 8 | 0 | 7 |
17 | 18 | 16 | -1 | 0 |
18 | 39 | 6 | 0 | 9 |
19 | 20 | 18 | -1 | 0 |
20 | 42 | 8 | 0 | 10 |
21 | 32 | 12 | 1 | 2 |
22 | 36 | 10 | 1 | 2 |
23 | 24 | 22 | -1 | 0 |
24 | 60 | 8 | 0 | 20 |
25 | 31 | 20 | 0 | 1 |
26 | 42 | 12 | 1 | 2 |
27 | 40 | 18 | 0 | 4 |
28 | 56 | 12 | 0 | 12 |
29 | 30 | 28 | -1 | 0 |
30 | 72 | 8 | -1 | 20 |
31 | 32 | 30 | -1 | 0 |
32 | 63 | 16 | 0 | 15 |
33 | 48 | 20 | 1 | 2 |
34 | 54 | 16 | 1 | 2 |
35 | 48 | 24 | 1 | 2 |
36 | 91 | 12 | 0 | 31 |
37 | 38 | 36 | -1 | 0 |
38 | 60 | 18 | 1 | 2 |
39 | 56 | 24 | 1 | 2 |
40 | 90 | 16 | 0 | 26 |
41 | 42 | 40 | -1 | 0 |
42 | 96 | 12 | -1 | 24 |
43 | 44 | 42 | -1 | 0 |
44 | 84 | 20 | 0 | 16 |
45 | 78 | 24 | 0 | 12 |
46 | 72 | 22 | 1 | 2 |
47 | 48 | 46 | -1 | 0 |
48 | 124 | 16 | 0 | 44 |
49 | 57 | 42 | 0 | 1 |
50 | 93 | 20 | 0 | 13 |
51 | 72 | 32 | 1 | 2 |
52 | 98 | 24 | 0 | 18 |
53 | 54 | 52 | -1 | 0 |
54 | 120 | 18 | 0 | 30 |
55 | 72 | 40 | 1 | 2 |
56 | 120 | 24 | 0 | 32 |
57 | 80 | 36 | 1 | 2 |
58 | 90 | 28 | 1 | 2 |
59 | 60 | 58 | -1 | 0 |
60 | 168 | 16 | 0 | 4 |
61 | 62 | 60 | -1 | 0 |
62 | 96 | 30 | 1 | 2 |
63 | 104 | 36 | 0 | 14 |
64 | 127 | 32 | 0 | 31 |
65 | 84 | 48 | 1 | 2 |
66 | 144 | 20 | -1 | 32 |
67 | 68 | 66 | -1 | 0 |
68 | 126 | 32 | 0 | 22 |
69 | 96 | 44 | 1 | 2 |
70 | 144 | 24 | -1 | 28 |
71 | 72 | 70 | -1 | 0 |
72 | 195 | 24 | 0 | 3 |
73 | 74 | 72 | -1 | 0 |
74 | 114 | 36 | 1 | 2 |
75 | 124 | 40 | 0 | 14 |
76 | 140 | 36 | 0 | 24 |
77 | 96 | 60 | 1 | 2 |
78 | 168 | 24 | -1 | 36 |
79 | 80 | 78 | -1 | 0 |
80 | 186 | 32 | 0 | 58 |
81 | 121 | 54 | 0 | 13 |
82 | 126 | 40 | 1 | 2 |
83 | 84 | 82 | -1 | 0 |
84 | 224 | 24 | 0 | 80 |
85 | 108 | 64 | 1 | 2 |
86 | 132 | 42 | 1 | 2 |
87 | 120 | 56 | 1 | 2 |
88 | 180 | 40 | 0 | 44 |
89 | 90 | 88 | -1 | 0 |
90 | 234 | 24 | 0 | 78 |
91 | 112 | 72 | 1 | 2 |
92 | 168 | 44 | 0 | 28 |
93 | 128 | 60 | 1 | 2 |
94 | 144 | 46 | 1 | 2 |
95 | 120 | 72 | 1 | 2 |
96 | 252 | 32 | 0 | 92 |
97 | 98 | 96 | -1 | 0 |
98 | 171 | 42 | 0 | 17 |
99 | 156 | 60 | 0 | 18 |
100 | 217 | 40 | 0 | 57 |
この表を見ていると、いろいろなことに気付く。
nが素数のとき、μ(n)=−1である。
このとき σ(n)+φ(n)≡0 (mod n) となる(これは証明できる)。
では、σ(n)+φ(n)≡0 (mod n) のとき、nは必ず素数となるか?
μ(n)=0かつ σ(n)+φ(n)≡1 (mod n) となるのは、
n=i2、iが素数のときに限る(これも証明できそう)。
σ(n)+φ(n)≡2 (mod n) のとき、μ(n)=1。
では、μ(n)=1のとき、必ずσ(n)+φ(n)≡2 (mod n) となるか?
答えを云ってしまうと、
1.はならない。最小の反例は312。
3.もならない。最小の反例は210。
前 | この章の目次 | 次 |
---|