1からnまでの自然数の中で, n と互いに素である目然数の個数を」
| Action》 互いに素である自然数の個数は, 互いに素でない自然数の個数から考。
正の整数 N を素因数分解して, N =がg"r"·… (p, 9, r, ·…… は素数)と表されると
となることが知られている。この関数φ(N) をオイラー関数という。
例題 236 互いに素である整。
(3) f(が)
問題編
(2) S(b)
225 (1)
(1) S(100)
条件の言い換え
補集合を考える
226 (1)
数は2または5の倍数である。
ここで,1から 100 までの自然数の中に
2の倍数は 50個,5の倍数は 20個,10 の倍数は10個
よって,2または5の倍数は
50+20-10 = 60 (個)
227 (1)
(2
100 = 2×50,
100 =
)3D5X20,
100 = 10× 10
n(AUB)
=n{A)+mB-
したがって
f(100) = 100-60 = 40
(2) かは素数であるから, 1からかまでの目然数の中で小 ←具特:
bと互いに素でない自然数はかのみである。
228
1
| fにい
したがって
f(p) = p-1
229
(3) 1からがまでのが個の自然数に含まれる かの倍数は
b, 2p, 36,
……, がかのがー個
4(1) と同様に
が= DXがよ)
が1個と考えても
したがって
f(p")= p"- p"-1
人力
230
S
Point オイラー関数
き,1から Nまでの正の整数の中で N と互いに素である整数の個数は
K) =A1 )… (0)
例えば,例題 236 (1) は
183
e00) -101-1-100 吉三0
9(100) =
23
14
: 40
25
のフロセス