トップ› 名古屋大学› 2003年› 文系第3問

名古屋大学 2003年文系第3問解説

方針・初手

$f(n)$ は、$n$ 以下の自然数の中で $n$ と互いに素であるものの個数を表している。このような個数を数える際は、条件を満たすものを直接数え上げるよりも、全体から「$n$ と互いに素でない数」すなわち「$n$ の素因数の倍数」を除外する（余事象を考える）方針が有効である。素因数が複数ある場合は、集合の考え方（包除原理）を用いて重複部分の処理を行う。

解法1

(1)

$15 = 3 \times 5$ であるから、$15$ と互いに素であるとは、$3$ の倍数でも $5$ の倍数でもないということである。 $1$ から $15$ までの自然数の全体集合を $U$、$3$ の倍数の集合を $A$、$5$ の倍数の集合を $B$ とすると、それぞれの要素の個数は以下のようになる。

$$n(U) = 15$$

$$n(A) = \frac{15}{3} = 5$$

$$n(B) = \frac{15}{5} = 3$$

また、$A \cap B$ は $3$ と $5$ の公倍数、すなわち $15$ の倍数の集合であるから、

$$n(A \cap B) = 1$$

$15$ と互いに素でない自然数の個数は、$n(A \cup B)$ であり、

$$n(A \cup B) = n(A) + n(B) - n(A \cap B) = 5 + 3 - 1 = 7$$

したがって、$1$ から $15$ までの自然数の中で $15$ と互いに素であるものの個数 $f(15)$ は、

$$f(15) = n(U) - n(A \cup B) = 15 - 7 = 8$$

(2)

$1$ から $pq$ までの自然数のうち、$pq$ と互いに素でないものは、$p$ の倍数または $q$ の倍数である。 $1$ から $pq$ までの自然数の全体集合を $U$、$p$ の倍数の集合を $A$、$q$ の倍数の集合を $B$ とすると、

$$n(U) = pq$$

$A = \{p, 2p, \dots, qp\}$ より、

$$n(A) = q$$

$B = \{q, 2q, \dots, pq\}$ より、

$$n(B) = p$$

$p, q$ は互いに異なる素数であるから、$A \cap B$ は $pq$ の倍数の集合となる。$1$ から $pq$ までの間に $pq$ の倍数は $pq$ 自体の $1$ 個のみであるから、

$$n(A \cap B) = 1$$

$pq$ と互いに素でない自然数の個数 $n(A \cup B)$ は、

$$n(A \cup B) = n(A) + n(B) - n(A \cap B) = q + p - 1$$

したがって、求める個数 $f(pq)$ は全体からこれを除いたものであるから、

$$f(pq) = n(U) - n(A \cup B) = pq - (p + q - 1) = pq - p - q + 1 = (p-1)(q-1)$$

解説

オイラーのトーティエント関数（$\varphi$ 関数）に関する非常に基本的な問題である。ある自然数 $n$ と互いに素な数の個数を求める場合、素因数分解を行い、それぞれの素因数の倍数を全体から引くのが定石である。

本問の (2) で導出した $f(pq) = (p-1)(q-1)$ という結果は、RSA暗号などの現代の整数の理論においても極めて重要な性質であり、公式として結果やその導出方法を記憶しておくことが望ましい。(1) は公式を知っていれば $f(15) = f(3 \times 5) = (3-1)(5-1) = 8$ と瞬時に確かめることができる。