-
![]()
482
00000
重要 例題 114 互いに素である自然数の個数
nを自然数とするとき.msnで、mとnが互いに素であるような自然数
個数をf(n) とする。また,g は素数とする。
(1) f(15) の値を求めよ。
(2)
(3) 自然数に対し, f (p) を求めよ。
基本112,113)
指針 (1) 15 と互いに素である15以下の自然数の個数を求めればよい。 15=3.5であるから
15 と互いに素である自然数は、3の倍数でもうの倍数でもない自然数である。しかも
「でない」の個数を求めるのは一般に面倒なので, 全体一(である) の方針で考える。
gf(pg) を求めよ。
(2) g は異なる素数であるから, pg と互いに素である自然数は, pの倍数でもgの倍
数でもない自然数である。 (1) と同様, 全体 (である)の方針で考える。
(3) 互いに素である自然数は,の倍数でない自然数である。
解答
(1) 153・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) pg は異なる素数であるから, pg と互いに素である自然
数は, pの倍数でもgの倍数でもない自然数である。
ゆえに,f(pg) は, 1からpg までのpg 個の自然数のうち
p,2p,....... (g-1)p, pgig, 2g, ......, (-1)g, pq
を除いたものの個数である。
よって
f(pa)=pq-(p+q−1)
= pg-p-g+1
=(-1)(g-1)
の倍数
(9個)
① は素数, kは自然数のとき
② pg は異なる素数のとき
②' gは互いに素のとき
pg(1個)
(3) 1からがまでの個の自然数のう
ちかの倍数は÷p=p1(個) ある
から、f(p) はかの倍数でないものの個数を求めて
f(p²)=p²-pk-1
gの倍数
(個)
1~pq
れの
〔類名古屋大]
p.gと
互いに素
練習
③ 114 (1) f(77) の値を求めよ。
(2) f(pg) = 24 となる2
(3) f(3) = 54 となる自然数kを求めよ。
15程度であれば、左の解答
でも対応できるが、数が大
きい場合には,第1章の基
本例題1で学習した, 集合
の要素の個数を求める要領
で考える。
pg が重複していることに
注意。
TO
検討 オイラー関数(n)
はギリシア文字で 「ファイ」 と読む。
nは自然数とする。 1からnまでの自然数で, n と互いに素であるものの個数をΦ(n) と表す。
この(n) をオイラー関数といい, 次の性質があることが知られている。
p(p)=p-1, $(p²)=p²-pk-1
上の重要例題114のf(n) について,次の問いに答えよ。
[(1) で確認] p=3,g=5
とするとf(15)=f(3.5)
=(3-1)(5−1)=2・4=8
$(pq)=$(p)$(q)=(p-1)(q−1)
Φ(pg) =Φ(p)(g)
(1-1/21) としてもよい。
g (p<g) の組をすべて求めよ。
つの素数p,
〔類 早稲田
(p.484E】
