mとnが互いに柔であるような自然
482
重要 例題114 互いに素
(2)pとqは異なる素数であるから,pqと互いに素である自然数は,pの倍数でもqo
15と互いに素である自然数は,3の倍数でも5の倍数でもない自然数である。しかし、
(2) カキqのとき,f(pq)を求めよ。
個数を(n)とする。また,p, qは素数とする。
(1) f(15)の値を求めよ。
(3)自然数をに対し,f(か)を求めよ。
mの
(限名古屋
基本112,19
(3) がと互いに素である自然数は, pの倍数でない自然数である。
415程度であれば、左の船
でも対応できるが,数が
きい場合には,第1の
本例題1で学習した、 鶏
の要素の個数を求める数
で考える。
解答
(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,qは異なる素数であるから, pq と互いに素である自然
数は,かの倍数でもgの倍数でもない自然数である。
ゆえに,f(bg)は, 1から 加までのpa 個の自然数のうち
p, 2p, …
を除いたものの個数である。
(q-1)か, pq;q, 20,
(p-1)q, pq
Apa が重複していることに
1~pq-
注意。
かの倍数
(q個)
9の倍数
(個)
[(1)で確認] p=3, q5
とすると f(15)=fB1
よって
f(bq)=pq-(b+q-1)
= Dg-p-g+1
=(3-1)(5-1)=21-
=(b-1)(q-1)
pq(1個)
p,qと
互いに素
(3) 1からがまでのが個の自然数のう
ち、pの倍数はがカ=が (個) ある
から,f(が)はpの倍数でないものの個数を求めて
f(が)=がーが
k-1
GSC
1-)としてもはい。
k-1
検討)オイラー関数φ(n)
nは自然数とする。1からnまでの自然数で, nと互いに素であるものの個数をのれ) C
この(n)をオイラー関数 といい, 次の性質があることが知られている。
①かは素数, kは自然数のとき
② かとqは異なる素数のとき
②かとqは互いに素のとき
ゆはギリシア文字で 「ファイ」 と読む。
(p)=p-1, (が)=Dかーかー!
(pg)=¢(b)(q)=(p-1)(q-1)
(pq)=(p)(q)
練習
上の重要例題114のf(n) について、次の間いに前
114|(1) f(77) の値を市
吊瀬田本
「転
