482
A
00000
互いに素である自然数の個数
例題 ( 114)
[類名古屋大
nを自然数とするとき, m≦n で, mとnが互いに素であるような自然数mの
重要
個数をf(n) とする。 また, p, g は素数とする。
(1) f (15) の値を求めよ。
(3) 自然数に対し, f(p) を求めよ。
指針 (1) 15 と互いに素である 15 以下の自然数の個数を求めればよい。 15=3･5であるから
15 と互いに素である自然数は, 3の倍数でも5の倍数でもない自然数である。 しかし、
「でない」 の個数を求めるのは一般に面倒なので, 全体 (である)の方針で考える。
(2) は異なる素数であるから, bg と互いに素である自然数は, pの倍数でもgの倍
TRAND
数でもない自然数である。 (1) と同様, 全体 (である)の方針で考える。
(3) と互いに素である自然数は,かの倍数でない自然数である。
解答
(1) 15=3.5 であるから, f(15) は1から15までの自然数のう
ち,
1-3, 2-3, 3.3, 4.3, 1.5, 2.5, 3.5
を除いたものの個数であるから
f(15)=15-7=8
(2) p, g は異なる素数であるから, pg と互いに素である自然
数は,pの倍数でもgの倍数でもない自然数である。
ゆえに, f(pg) は, 1 から by までのby 個の自然数のうち D
p,2p,......, (q-1) p, paig, 2g, , (p-1)q, pq
を除いたものの個数である。
よって
f(pg) = pg-(p+α-1)
= pg-p-g+1
(2) gf (pg) を求めよ。
FRO
=(p-1) (q-1)
(3) 1からp までの個の自然数のう
の倍数はppp1(個)ある
から、f(p) はかの倍数でないものの個数を求めて
f(p)=p²-pk-1 ISMAI
①pは素数, kは自然数のとき
② p q は異なる素数のとき
②' p q は互いに素のとき
pの倍数
(9個)
練習
(3)
③ 114 (1)
f(77) の値を求めよ。
gの倍数
(個)
1~pq
pg(1個)
bigと
互いに素
基本112,113)
15 程度であれば,左の解答
でも対応できるが,数が大
きい場合には,第1章の基
本例題1で学習した, 集合
の要素の個数を求める要領
で考える。
検討 オイラー関数(n)
CADRE
n は自然数とする。1からnまでの自然数で, n と互いに素であるものの個数をΦ(n) と表す。
このΦ(n) をオイラー関数といい, 次の性質があることが知られている。
$(p)=p-1,
(p²)=p²-pk-1
(pa)=(p)o(q)
上の重要例題 114 の f (n) について,次の問いに答えよ。
<pg が重複していることに
注意。
はギリシア文字で「ファイ」と読む。
[(1) で確認] p=3,g=5
とするとf(15)=f(3.5)
=(3-1)(5-1)=2.4=8
(pa)=(p)o(q)=(p-1)(q-1)
(1-1/2)としてもよい。
(2) f (pg) = 24 となる2つの素数p, g (p<g) の組をすべて求めよ。
(3) f(3) = 54 となる自然数kを求めよ。
[類 早稲田大〕
1
STT
p.484 EX80
基本
2
(2)
CHA
解
(I) 20
素因
1か
1
