配布プリント

計算機数学演習 A 2015.7.8. オイラー関数
この講義の資料は, http://www.sm.u-tokai.ac.jp/~nakayama/ より入手することができる.
オイラー関数の計算
1
定義 1. 自然数 n について,
φ(n) = (1, 2, . . . , n の中で n と互いに素な数の個数)
と定義し, オイラー関数と呼ぶ.
例 2. φ(10) を計算する. 1 から 10 の中で, 10 と互いに素 (すなわち, 10 との最大公約数が 1 となる) のは, 1, 3, 7, 9 で
あるから φ(10) = 4.
問題 3. オイラー関数 φ(5), φ(6), φ(15) を計算せよ.
1. 素朴にオイラー関数を計算するプログラム euler.txt
def phi(N)
{
C = 0;
for (I = 1; I < N; I++) {
if (igcd(I, N) == 1) {
C++;
}
}
return C;
}
end$
/* igcd(I, N) は整数 I と整数 N の最大公約数を計算する関数 */
/* I と N が互いに素の場合の処理 */
問題 4. φ(1), φ(2), . . . , φ(100) をプログラムを使い表示せよ.
命題 5. 素数 p について,
φ(p) = p − 1,
φ(pa ) = pa − pa−1 (a は自然数)
が成り立つ.
問題 6. オイラー関数 φ(97), φ(132 ), φ(210 ), φ(3100 ) を計算せよ.
命題 7. 正の整数 a, b が互いに素の時,
φ(ab) = φ(a)φ(b)
が成り立つ.
例 8. φ(35) = φ(5)φ(7) = 4 · 6 = 24 が成り立つことを確認する. (上の命題で a, b が素数である場合の例)
1, 2, 3 . . . , 35 を 5 × 7 の表に書くと下の表になる. ここから 5 と互いに素でない数を消し, 7 と互いに素でない数を消
して残った数が 35 と互いに素な数である.
1
6
11
16
21
26
31
2
7
12
17
22
27
32
3
8
13
18
23
28
33
4
9
14
19
24
29
34
5
10
15
20
25
30
35
1
例 9. φ(36) = φ(4)φ(9) = 2 · 6 = 12 が成り立つことを確認する. (上の命題で a, b が素数でない場合の例)
1, 2, 3 . . . , 36 を 4 × 9 の表に書くと下の表になる. ここから 4 と互いに素でない数を消し, 9 と互いに素でない数を消
して残った数が 35 と互いに素な数である.
1
5
9
13
17
21
25
29
33
2
6
10
14
18
22
26
30
34
3
7
11
15
19
23
27
31
35
4
8
12
16
20
24
28
32
36
例 10.
φ(15) = φ(3 · 5) = φ(3)φ(5) = (3 − 1)(5 − 1) = 2 · 4 = 8
φ(100) = φ(22 · 52 ) = φ(22 )φ(52 ) = (22 − 2)(52 − 5) = 2 · 20 = 40
このようにオイラー関数は大きな数であっても, 素因数分解ができれば手でも計算できる.
問題 11. オイラー関数 φ(10), φ(1000), φ(30), φ(10n ) を計算せよ.
2. 素朴に素因数分解をするプログラム factorize.txt
def factorize(N)
{
F = 2;
while (F * F <= N) {
if (N % F == 0) {
print(F);
N = idiv(N, F);
} else {
F++;
}
}
if (N != 1)
print(N);
}
end$
/* F : 素因数を保存する変数 */
/* N が F で割り切れた場合の処理 */
/* idiv(N, F) は N を F で割った商を返す関数 */
/* N が F で割り切れなければ F を 1 増やす */
問題 12. 上のプログラムを用いて, 111111 を素因数分解し, φ(111111) を計算せよ.
例 13. Asir において素因数分解, オイラー関数の計算をするのに, pari(factor, 数), pari(phi, 数) という命令が用
意されている. (ここで pari とは数論用ソフト PARI のことであり, Asir から PARI の関数を呼び出す命令である.)
3. Asir での素因数分解, オイラー関数の計算
[1854] pari(factor, 10000);
[ 2 4 ]
[ 5 4 ]
[1856] pari(phi, 10000);
4000
[1857] pari(phi, 111111);
51840
10000 の素因数分解
[素因子, 指数]
オイラー関数 \phi(10000) の計算
オイラー関数 \phi(111111) の計算
問題 14. オイラー関数 φ(123456789) を計算機を使って計算せよ.
2
参考文献
[1] 木田祐司, 初等整数論, 朝倉書店
[2] D. ハーディー, C. ウォーカー, 応用代数学入門, ピアソンエデュケーション
3

Download Report