1 約数と倍数
Check
OA3 互いに素な自然数の個数
431
題
243
nを自然数とする. mSnでmとnが互いに素である自然数mの個数
をノカ)とするとき,次の問いに答えよ、
D f(15) を求めよ、
(2) S(ba)を求めよ、ただし、p, qは異なる素数とする。
(3) f(が)を求めよ、ただし, pは素数, kは自然数とする. (名古屋大 改)
33
は、
とに
照)
え方(1) 15=3·5 であるから, f(15) は,15 以下の自然数で15と互いに素,つまり,3の倍
数でも5の倍数でもない自然数の個数を表す。
19) カとqは異なる素数であるから, pq と互いに素である自然数は,pの倍数でもqの
倍数でもない自然数である。
(3) がと互いに素である自然数は, かの倍数でない自然数である。
(1) 15=3·5 であるから, 15 と互いに素でない自然数,
すなわち, 3の倍数または5の倍数であり,15以下の否定「互いに素でな
自然数は,3,6,9, 12, 15, 5, 10の7個である。
よって,15 と互いに素な自然数の個数は,
f(15)=15-7=8
「互いに素である」の
して
れな
い」を考える。
このf(n)をオイラー
関数という. (か.432
Column 参照)
(2)か, qは異なる素数であるから, pqと互いに素でな
い自然数,すなわち, かの倍数またはgの倍数であり,
pg以下の自然数は、p)
bの倍数 1·6, 2·p, …; (q-1)か, p加の@個
gの倍数 1·q, 2.q, …, (カー1)q, pgのか個
pqの倍数 pq
より,
(1)を一般的に考える。
p=3, q=5 としてみ
ると見通しがよくなる。
pq-p=q(個)
| pq-q=p(個)
の1個
(q+カ-1)個
よって,pg と互いに素な自然数の個数は,
『(bq)= pq-(q+カ-1) -0 1 (3-8- 08n
= g-カ-q+1==(カ-1)(q-1)
D, kは自然数であるから, が以下の自然数はが、 ド
個ある。
かは素数であるから,が以下の自然数でかの倍数
は全部で,
したがって,
お志
S お米
がーカ=が-1(個)
k-1
第8章
F(か)=がーが 50
Focus
いに素である自然数の個数は,補集合の考えを利用せよ
合5
大はマお
脂
T次の問いに答えよ,ただし, pqは異なる素数
グレーの丸で囲んであるところでと赤の丸のところと青のところで全部でpqを3回数えているんですか?