nを自然数とするとき, mSnで, mとnが互いに素であるような自然数 mの個個数をf (n) と
よって,a+6
練習 nを自然数とするとき, mSnで, mとnが互いに素であるような自然数 mn の個数を {
114 する。
0
(1)f(77) の値を求めよ。
(2) F(bg)=D24 となる2つの素数p, q(か<q)の組をすべて求めよ。
(3) f(3*)=D54 となる自然数kを求めよ。
【類早稲田大)
(1) 77=7·11 であり, 7と11は互いに素である。
f(77) は1から77 までの 77個の自然数のうち,
大量「+ 1-
|-7-11 が重複している
ことに注意。
を除いたものの個数である。
そオイラー関数の性質よ
り(7-11)=¢(7)φ(11)
=(7-1)(11-1)=60
茶自
(カ-1)(q-1)=24 とすると, 1<pー1<q-1であるから か>2であるから
p-122-1
よって
f(77)=77-(11+7-1)=77-17=60
(2) [重要例題114 (2) の結果を用いる]
p, q(か<q)は素数であるから
f(ba)=(p-1)(q=1)
(カ-1, q-1)=(1, 24), (2, 12), (3, 8), (4, 6)
ゆえに
(b, q)=(2, 25), (3, 13), (4, 9), (5, 7) 1+ S1-
p, qがともに素数である組は
(3) [重要例題114 (3) の結果を用いる]
かは素数, kは自然数とするとき, f(が)=Dがーがー1が成り立つ
(p, q)=(3, 13), (5, 7)
から
f(3*)=3*-34-1=34-1(3-1]=2·34-1
EIT
54=2-39 であるから, f(3*)=54とすると
2-34-1=2-3°
そ素因数分解の一意性
(本冊p.471 参照)。
指数部分を比較して
k-1=3
よって
k=4
士ロ
