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

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

解

$262144$

$p=43,q=47,n=2021$ おく。$m=(pq)^n$ 以下の正整数全体の集合を $U$，$m$ 以下の正整数のうち $p$ で割り切れるもの全体の集合を $P$，$m$ 以下の正整数のうち $q$ で割り切れるもの全体の集合を $Q$ とする。また，整数の集合 $X$ に対し，$X$ の要素の総和を $s(X)$ とする。このとき $$\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}$$ よって $$\dfrac{S(m)}{m^2}=\dfrac{1}{2}\cdot\dfrac{42}{43}\cdot\dfrac{46}{47}=\dfrac{966}{2021}$$ が得られる。

解

$\dfrac{966}{2021}$

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

$$\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)=\dfrac{n\phi(n)}{2}$ を得る。

(1)

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

(2)

$$\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}$$ より $$\dfrac{S(m)}{m^2}=\dfrac{966}{2021}$$

$n$ の素因数分解を $$n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}\ \; (p_1<p_2\cdots<p_k)$$ とする。このとき $$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)$ が偶数となるための必要十分条件は，上式の右辺の分子を $4$ で割り切れることである。

1. $n=2$ のとき $S(2)=1$ より奇数である。
2. $n$ が $4$ 以上の $2$ べきのとき $n$ は $4$ で割り切れるから $S(n)$ は偶数である。
3. $n$ が $2$ べきでない偶数のとき $n$ はある奇素数 $p_i$ をもつ。このとき $n(p_i^{a_i}-p_i^{a_i-1})$ は $4$ の倍数であるため $S(n)$ は偶数である。
4. $n$ が二つ以上の異なる奇素数 $p_i,p_j$ を持つとき $(p_i^{a_i}-p_i^{a_i-1})(p_j^{a_j}-p_j^{a_j-1})$ は $4$ の倍数であるため $S(n)$ は偶数である。
5. $n$ が $p\equiv 3 \pmod 4$ なる素数 $p$ と正整数 $k$ を用いて $n=p^k$ となるとき，$p^k-p^{k-1}=p^{k-1} (p-1)$ は2でちょうど1回割り切れる。$S(n)$ の分子 $p^{2k-1} (p-1)$ は4の倍数にならないため，$S(n)$ は奇数になることが分かる。
6. $n$ が $p\equiv 1 \pmod 4$ なる素数 $p$ と正整数 $k$ を用いて $n=p^k$ となるとき，$p^k-p^{k-1}=p^{k-1} (p-1)$ は4の倍数になるため，$S(n)$ は偶数になることが分かる。
7. $n=1$ のとき $S(1)=1$ より奇数である。

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