Evolton

名古屋大学 2003年度 前期日程 第2次学力試験 整数・場合の数文系数学 第3問(a)

nを自然数とするとき,m≦nでmとnの最大公約数が1となる自然数mの個数をf(n)とする.

(1) f(15)を求めよ.

(2) p,qを互いに異なる素数とする.このときf(pq)を求めよ.

難易度3/ 10計算量3/ 10目安10分

整数、場合の数 最大公約数、数え上げ、包除原理

方針

f(n) は 1 から n までのうち n と互いに素なものの個数である。(1)は 15=3⋅5 なので、3の倍数と5の倍数を除いて数える。(2)は pq と互いに素でない数が、p の倍数または q の倍数であることを使い、重複する pq だけを一度戻す。

解答

(1) 15=3⋅5 である。1 から 15 までの自然数のうち、15と互いに素でないものは、3の倍数または5の倍数である。

3の倍数は 3,6,9,12,15 の5個、5の倍数は 5,10,15 の3個である。このうち15は重複して数えているので、15と互いに素でないものは 5+3−1=7 個である。したがって f(15)=15−7=8 である。実際、互いに素なものは 1,2,4,7,8,11,13,14 である。

(2) p,q は互いに異なる素数である。1 から pq までの自然数のうち、pq と互いに素でないものは、p の倍数または q の倍数である。 p の倍数は p,2p,…,qp の q 個であり、q の倍数は q,2q,…,pq の p 個である。両方に含まれるものは pq だけである。したがって、pq と互いに素でないものは p+q−1 個である。

よって f(pq)=pq−(p+q−1)=pq−p−q+1 であり、f(pq)=(p−1)(q−1) である。

別解

解法2(選べる剰余を積で数える)

方針

素数 p ごとに p の倍数を避け、さらに素数 q の倍数を避ける。中国剰余定理を使わず、1,…,pq を p 個ずつのブロックに分けて数える。

解答

(1)

1,…,15 のうち、3でも5でも割り切れないものは1,2,4,7,8,11,13,14の8個である。よって f(15)=8 である。

(2)

1,…,pq を1,…,p;p+1,…,2p;…;(q−1)p+1,…,qpの q 個のブロックに分ける。

各ブロックには p の倍数が1個あるので、それを除くと p−1 個が残る。また、q の倍数は全体で p 個あるが、そのうち pq はすでに p の倍数として除かれている。したがって追加で除くのは p−1 個である。

よってf(pq)=q(p−1)−(p−1)=(p−1)(q−1).

総評

互いに素でない数を「素因数の倍数」として除く基本問題である。目安時間は6〜10分。(1)では直接列挙でもよいが、3の倍数と5の倍数の包除で数えると(2)につながる。(2)では p と q が異なる素数であるため、両方の倍数として重なるのは pq だけである。この1個を戻すことを明記すれば、(p−1)(q−1) への整理も自然に出る。

Evolton Pro

月額
2,480円(税込)
保存・印刷
公開過去問PDF・オーダーメイド問題集PDF
プランを確認・登録

冊子PDFで見る名大の整数の問題で問題集を作る

出典: 名古屋大学 2003年度 前期 数学。問題文はHTML表示のために再入力・数式組版しています。