入試数学コンテスト第3回第5問解答解説

更新日時 2021/10/30
目次
  • 第5問 [整数]

第5問 [整数]

第5問

正の整数 nn に対し,nn 以下で nn と互いに素であるような正の整数の総和を S(n)S(n) とする。

例えば,S(1)=1S(5)=1+2+3+4=10S(6)=1+5=6S(1)=1,S(5)=1+2+3+4=10,S(6)=1+5=6 である。

以下の問いに答えよ。

(1) S(1024)S(1024) を求めよ。

(2) m=20212021m=2021^{2021} とするとき,S(m)m2\dfrac{S(m)}{m^2} の値を求めよ。

(3) S(n)S(n) が偶数となるような 100100 以下の正整数 nn の総和を求めよ。

第5問は整数の問題です。

まずは簡単な2のべき乗のケースを考えます。2のべき乗と互いに素な整数は,その整数以下の奇数になります。

第5問(1)

1024=2101024=2^{10} であるから,求めるものは 10241024 以下の奇数の正整数の総和である。したがって S(1024)=k=1512(2k1)=512513512=262144 S(1024)=\displaystyle \sum _{k=1}^{512} (2k-1)=512\cdot513-512=262144 が得られる。

262144262144

次は2つの素数の積の場合を計算します。補集合のアイデアをうまく活用します。

20212021 と互いに素である整数は,4343 でも 4747 割り切れない整数になります。そのため 20212021 以下の整数で 43434747 で割り切れる整数の集合を持ってきて,これの補集合を考えればよいのです。

202120212021^{2021} 以下の整数のうち 4343 で割り切れるもの全体の集合を PP4747 で割り切れるもの全体の集合を QQ としましょう。

このとき 20212021 と互いに素ではない整数の集合は,PQP \cup Q です。したがって PQP \cup Q の要素をすべて足した数を,11 から 202120212021^{2021} まで足した数から引けば求める数がわかりますね。

PQP \cup Q の要素をすべて足した数は PP の要素をすべて足した数と QQ の要素をすべて足した数から,重複である PQP \cap Q の要素をすべて足した数を引けば得られます。

第5問(2)

p=43,q=47,n=2021p=43,q=47,n=2021 おく。m=(pq)nm=(pq)^n 以下の正整数全体の集合を UUmm 以下の正整数のうち pp で割り切れるもの全体の集合を PPmm 以下の正整数のうち qq で割り切れるもの全体の集合を QQ とする。また,整数の集合 XX に対し,XX の要素の総和を s(X)s(X) とする。このとき S(m)=s(U)s(P)s(Q)+s(PQ)=k=1pnqnkpk=1pn1qnkqk=1pnqn1k+pqk=1pn1qn1k=12pnqn(pnqn+1)p2pn1qn(pn1qn+1)q2pnqn1(pn1qn+1)+pq2pn1qn1(pn1qn1+1)=12pnqn(pnpn1)(qnqn1)=12m2(11p)(11q)\begin{aligned} S(m) &=s(U)-s(P)-s(Q)+s(P\cap Q)\\ &=\sum_{k=1}^{p^n q^n} k - p\sum _{k=1}^{p^{n-1}q^n} k - q\sum _{k=1}^{p^nq^{n-1}}k+ pq \sum_{k=1}^{p^{n-1} q^{n-1}}k \\ &=\dfrac{1}{2} p^nq^n(p^nq^n+1) - \dfrac{p}{2} p^{n-1} q^n (p^{n-1} q^n + 1) - \dfrac{q}{2} p^n q^{n-1} (p^{n-1} q^n + 1) + \dfrac{pq}{2} p^{n-1} q^{n-1} (p^{n-1} q^{n-1} + 1) \\ &=\dfrac{1}{2} p^n q^n (p^n-p^{n-1}) (q^n-q^{n-1}) \\ &=\dfrac{1}{2} m^2 \left(1-\dfrac{1}{p}\right) \left(1-\dfrac{1}{q}\right) \end{aligned} よって S(m)m2=1242434647=9662021 \dfrac{S(m)}{m^2}=\dfrac{1}{2}\cdot\dfrac{42}{43}\cdot\dfrac{46}{47}=\dfrac{966}{2021} が得られる。

9662021\dfrac{966}{2021}

実はより一般的に S(n)S(n) を計算することができる公式を得ることができます。

(2) の答えをよく見てみましょう。分母は 20212021 になっていますね。分子を見てみましょう。966=19322=42462966 = \dfrac{1932}{2} = \dfrac{42 \cdot 46}{2} となっています。これらを踏まえると (2) の答えが 12(1143)(1147)\dfrac{1}{2} \cdot\left(1-\dfrac{1}{43}\right)\cdot\left(1-\dfrac{1}{47}\right) であることに気付くのではないでしょうか。

ここでオイラーのファイ関数 ϕ(n)\phi(n) を用いると S(n)=nϕ(n)2S(n) = \dfrac{n \phi(n)}{2} となるのではないかと予想できます。そしてこれは実際に正しいのです。

オイラーのファイ関数に馴染みがない人は オイラーのファイ関数のイメージ をチェックしてください。

第5問(1)(2) 別解

n,k  (k<n)n,k \; (k<n) が互いに素のとき,互除法より n,nkn,n-k もまた互いに素である。よって

2S(n)=21kngcd(k,n)=1k=1kngcd(k,n)=1k+1kngcd(k,n)=1(nk)=1kngcd(k,n)=1n=nϕ(n)\begin{aligned} 2S(n) &= 2 \sum_{\substack{1\leq k \leq n \\ \gcd(k,n)=1}} k\\ &=\sum_{\substack{1\leq k \leq n \\ \gcd(k,n)=1}} k + \sum_{\substack{1\leq k \leq n \\ \gcd(k,n)=1}} (n-k) \\ &=\sum_{\substack{1\leq k \leq n \\ \gcd(k,n)=1}} n \\ &=n\phi(n) \end{aligned} より S(n)=nϕ(n)2S(n)=\dfrac{n\phi(n)}{2} を得る。

(1)

S(1024)=1024ϕ(1024)2=5121024(112)=262144\begin{aligned} S(1024) &= \dfrac{1024\phi(1024)}{2}\\ &=512\cdot1024\cdot\left(1-\dfrac{1}{2}\right)\\ &=262144 \end{aligned}

(2)

S(m)=mϕ(m)2=m22(1143)(1147)\begin{aligned} S(m)&=\dfrac{m\phi(m)}{2}\\ &=\dfrac{m^2}{2}\cdot\left(1-\dfrac{1}{43}\right)\cdot\left(1-\dfrac{1}{47}\right) \end{aligned} より S(m)m2=9662021\dfrac{S(m)}{m^2}=\dfrac{966}{2021}

(3) は別解で述べた「公式」を用いて計算をします。細かい場合分けをキチンとやることが必要になります。

第5問(3)

nn の素因数分解を n=p1a1p2a2pkak   (p1<p2<pk) n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}\ \; (p_1<p_2\cdots<p_k) とする。このとき S(n)=n(p1a1p1a11)(p2a2p2a21)(pkakpkak1)2 S(n)=\dfrac{n(p_1^{a_1}-p_1^{a_1-1})(p_2^{a_2}-p_2^{a_2-1})\cdots(p_k^{a_k}-p_k^{a_k-1})}{2} である。

S(n)S(n) が偶数となるための必要十分条件は,上式の右辺の分子を 44 で割り切れることである。

  1. n=2n=2 のとき S(2)=1S(2)=1 より奇数である。
  2. nn44 以上の 22 べきのとき nn44 で割り切れるから S(n)S(n) は偶数である。
  3. nn22 べきでない偶数のとき nn はある奇素数 pip_i をもつ。このとき n(piaipiai1)n(p_i^{a_i}-p_i^{a_i-1})44 の倍数であるため S(n)S(n) は偶数である。
  4. nn が二つ以上の異なる奇素数 pi,pjp_i,p_j を持つとき (piaipiai1)(pjajpjaj1)(p_i^{a_i}-p_i^{a_i-1})(p_j^{a_j}-p_j^{a_j-1})44 の倍数であるため S(n)S(n) は偶数である。
  5. nnp3(mod4)p\equiv 3 \pmod 4 なる素数 pp と正整数 kk を用いて n=pkn=p^k となるとき,pkpk1=pk1(p1)p^k-p^{k-1}=p^{k-1} (p-1) は2でちょうど1回割り切れる。S(n)S(n) の分子 p2k1(p1)p^{2k-1} (p-1) は4の倍数にならないため,S(n)S(n) は奇数になることが分かる。
  6. nnp1(mod4)p\equiv 1 \pmod 4 なる素数 pp と正整数 kk を用いて n=pkn=p^k となるとき,pkpk1=pk1(p1)p^k-p^{k-1}=p^{k-1} (p-1) は4の倍数になるため,S(n)S(n) は偶数になることが分かる。
  7. n=1n=1 のとき S(1)=1S(1)=1 より奇数である。

したがって S(n)S(n) が奇数になる 100100 以下の正整数 nn1237911192327314347495967717981831,2,3,7,9,11,19,23,27,31,43,47,49,59,67,71,79,81,83 なので,求める答えは k=1100k\displaystyle\sum_{k=1}^{100} k からこれらの総和を引いた 43384338 である。

オイラーのファイ関数の他にも整数論で重要な関数は多くあります。例えば下の記事で紹介されているメビウス関数などがあります。
メビウスの反転公式の証明と応用

また4で割って1余る素数と3余る素数で場合分けをしました。問題とは関係ないですが,4で割った余りで素数を分類することは,かなり大きな意義があります。

例えば フェルマーの二平方和定理 という重要な定理があります。これは4で割って 1余る素数は,2つの平方数の和で表されることを主張しています。この定理は ガウス整数 の集合で「素数」を考えるときにも関係してきます。興味のある人は勉強してみてください。