大阪大学(理系) 2024年 問題5
$自然数 \ 1,\ 2,\ 3,\ \cdots ,\ n\ のうち、n\ と互いに素であるものの個数を \ f(n)\ とする。$
$(1)\ \ 自然数 \ a,\ b,\ c\ および相異なる素数 \ p,\ q,\ r\ に対して、等式$
$\hspace{5em} f(p^a q^b r^c)=p^{a-1}q^{b-1}r^{c-1}(p-1)(q-1)(r-1)$
$\quad が成り立つことを示せ。$
$(2)\ \ f(n)\ が \ n\ の約数となる \ 5\ 以上 \ 100\ 以下の自然数をすべて求めよ。$
(1)
$解法Ⅰ\ \ (どちらかというと高校生向けの方法)$
$有限集合 \ A\ の要素の個数を \ n(A)\ で表すと、3\ つの集合の要素の個数について$
$n(A \cup B \cup C)=n(A)+n(B)+n(C)-n(A \cap B)-n(B \cap C)-n(C \cap A)+n(A \cap B \cap C) \quad だから$
\begin{eqnarray*} & &n(\overline{A} \cap \overline{B} \cap \overline{C})\\ \\ &=&n(\overline{A \cup B \cup C})\\ \\ &=&n(U)-n(A \cup B \cup C)\\ \\ &=&n(U)-n(A)-n(B)-n(C)+n(A \cap B)+n(B \cap C)+n(C \cap A)-n(A \cap B \cap C)\\ \end{eqnarray*} $が成りたつことをつかう。$
$n\ を自然数として、全体集合 \ U=\{1,\ 2,\ 3,\ \cdots , \ n\}\ \ (n=p^aq^br^c )\ \ のうち、$
$n\ と互いに素である(公約数をもたない)ものの個数は \ p,\ q,\ r \ の倍数でない数の個数である。$
$素数 \ p\ の倍数の集合を\ M(p) ,\ 要素の個数を \ |M(p)|\ と表すことにする。q,\ r についても同様である。$
$|M(p)|=\cfrac{n}{p},\quad |M(q)|=\cfrac{n}{q},\quad |M(r)|=\cfrac{n}{r},\quad |M(pq)|=\cfrac{n}{pq},\quad |M(qr)|=\cfrac{n}{qr},\quad |M(pr)|=\cfrac{n}{pr},$
$|M(pqr)|=\cfrac{n}{pqr} \quad だから$
\begin{eqnarray*} & &f(p^a q^b r^c)\\ \\ &=&|U|-|M(p)|-|M(q)|-|M(r)|+|M(pq)|+|M(qr)|+|M(pr)| -|M(pqr)|\\ \\ &=&n-\cfrac{n}{p}-\cfrac{n}{q}-\cfrac{n}{r}+\cfrac{n}{pq}+\cfrac{n}{qr}+\cfrac{n}{pr}-\cfrac{n}{pqr}\\ \\ &=&\cfrac{n}{pqr}(pqr-qr-pr-pq+r+p+q-1)\\ \\ &=&\cfrac{n}{pqr}\{(pq-p-q+1)r-(pq-p-q+1)\}\\ \\ &=&\cfrac{n}{pqr}(pq-p-q+1)(r-1)\\ \\ &=&\cfrac{n}{pqr}(p-1)(q-1)(r-1)\\ \\ &=&p^{a-1}q^{b-1}r^{c-1}(p-1)(q-1)(r-1) \end{eqnarray*}
$解法Ⅱ(どちらかというとやや数学的な方法)$
(i)$\ \ f(p)=p-1 \ \ であることを証明する。$
$\quad p\ が素数ならば、1,\ 2,\ 3,\ \cdots , \ p-1 \ \ はすべて \ p\ と互いに素だから$
$\quad f(p)=p-1$
(ii)$\ \ f(pq)=f(p)f(q) \ \ であることを証明する。$
$\quad 1,\ 2,\ 3,\ \cdots,\ pq\ \ のうち$
$\quad p\ を公約数にもつのは \ \ p,\ 2p,\ 3p,\ \cdots , \ qp\ \ の \ q\ 個$
$\quad q\ を公約数にもつのは \ \ q,\ 2q,\ 3q,\ \cdots , \ pq \ \ の \ p\ 個$
$\quad これらは \ pq\ 以外すべて異なる数だから全部で \ \ p+q-1\ 個$
$\quad f(pq)=pq-(p+q-1)=(p-1)(q-1)=f(p)f(q)$
(iii)$\ \ f(p^a)=p^{a-1}(p-1)\ \ であることを証明する。$
$\quad 1,\ 2,\ 3,\ \cdots , \ p^a \ \ のうち \ p \ の倍数は$
$\quad 1\cdot p,\ \ 2\cdot p,\ \ 3\cdot p,\ \ \cdots , \ \ p^{a-1}\cdot p \ \ \ の \ p^{a-1}\ 個ある。$
$\quad よって、p\ の倍数でないもの、すなわち、p^a\ と互いに素であるものの個数は$
$\quad f(p^a)=p^a-p^{a-1}=p^{a-1}(p-1)$
$これらを用いて$
$f(p^a q^b r^c)=f(p^a)f(q^b r^c)=f(p^a)f(q^b)f(r^c)=p^{a-1}q^{b-1}r^{c-1}(p-1)(q-1)(r-1)$
(2)
$自然数 \ nをあらかじめ素因数分解しておく。$
(i)$\ \ n=p^a \ \ の形の数のとき$
$\quad f(n)=f(p^a)=p^{a-1}(p-1) \quad だから$
$\quad p-1=1 \ \ のとき、すなわち \ \ p=2\ \ のとき$
$\quad f(2^a)=2^{a-1} \ \ だから \ \ f(2^a)\ \ は \ 2^a \ の約数となる。$
$\quad この数は、2^3,\ \ 2^4,\ \ 2^5,\ \ 2^6 $
(ii)$\ \ n=p^a q^b\ \ (p < q)\ \ の形の数のとき$
$\quad f(n)=f(p^a q^b)=p^{a-1}q^{b-1}(p-1)(q-1) \quad だから$
$\quad p-1=1,\ \ q-1=p \ \ のときすなわち \ \ p=2,\ \ q=3 \ \ のとき$
$\quad f(2^a3^b)=2^{a-1}3^{b-1}\times 2=2^a3^{b-1}\ \ だから \ \ f(2^a3^b)\ \ は \ 2^a3^b \ \ の約数となる。$
$\quad この数は$
$\quad 2 \times 3 ,\ \ 2^2 \times 3, \ \ 2^3 \times 3 , \ \ 2^4 \times 3 ,\ \ 2^5 \times 3 $
$\quad 2 \times 3^2 ,\ \ 2^2 \times 3^2, \ \ 2^3 \times 3^2 $
$\quad 2 \times 3^3 $
$q\ が \ 3\ より大きな素数のときは$
(i)$\ \ 素数は奇数だから \ q-1 \ は偶数となり \ 2^m \ の項が生じる。$
$\quad その結果 \ \ m\ が \ 2^a \ の指数 \ a\ より大きくなる。例えば、f(2 \times 5)=(2-1)(5-1)=2^2$
(ii)$\ \ p,\ q\ 以外の素数が発生する。例えば 、f(2 \times 7)=(2-1)(7-1)=2 \times 3$
(i),(ii)$\ \ より \ \ f(n)\ は \ ｎ\ の約数ではない。$
$n=p^aq^br^c \ \ (p < q < r)\ \ の形の数についても$(i),(ii)$\ \ より \ f(n)\ が \ ｎ\ の約数となることはない。$
$以上求めた \ n\ を小さい順に並べると$
$\qquad 6,\ \ 8,\ \ 12,\ \ 16,\ \ 18,\ \ 24,\ \ 32,\ \ 36,\ \ 48,\ \ 54,\ \ 64,\ \ 72,\ \ 96\ の \ 13\ 個$
$(補充)$
$f(n) を「オイラー関数」といい、整数論では \ \varphi(n) \ とあらわされます。$
$詳しくは($オイラーの定理$)を参考にしてください。$
メインメニュー に戻る