(1) $p$ を素数とするとき、$3^p$ を $p$ で割った余りを求めよ。 (2) 100以下の自然数のうち、100と互いに素な自然数の個数を求めよ。 (3) $0 \cdot {}_{10}C_0 + 1 \cdot {}_{10}C_1 + \dots + 10 \cdot {}_{10}C_{10}$ の値を求めよ。

1. 問題の内容

(1) $p$ を素数とするとき、$3^p$ を $p$ で割った余りを求めよ。

(2) 100以下の自然数のうち、100と互いに素な自然数の個数を求めよ。

(3) $0 \cdot {}_{10}C_0 + 1 \cdot {}_{10}C_1 + \dots + 10 \cdot {}_{10}C_{10}$ の値を求めよ。

2. 解き方の手順

(1) フェルマーの小定理を利用する。$p$ が素数で、$a$ が $p$ の倍数でないとき、$a^{p-1} \equiv 1 \pmod{p}$ が成り立つ。

よって、$3^{p-1} \equiv 1 \pmod{p}$ が成り立つ。したがって、$3^p \equiv 3 \pmod{p}$。

したがって、求める余りは $3$ である。

(2) 100と互いに素な自然数の個数を求める。

$100 = 2^2 \cdot 5^2$ であるから、100以下の自然数の中で2の倍数または5の倍数であるものの個数を求め、全体から引く。

100以下の2の倍数は $100/2 = 50$ 個。

100以下の5の倍数は $100/5 = 20$ 個。

100以下の10の倍数は $100/10 = 10$ 個。

2の倍数または5の倍数の個数は $50 + 20 - 10 = 60$ 個。

したがって、100と互いに素な自然数の個数は $100 - 60 = 40$ 個。

別の解法として、オイラー関数を利用できる。$\phi(100) = \phi(2^2 \cdot 5^2) = \phi(2^2) \cdot \phi(5^2) = (2^2 - 2^1)(5^2 - 5^1) = (4-2)(25-5) = 2 \cdot 20 = 40$

(3) 二項定理を応用する。二項定理より、

$(1+x)^n = \sum_{k=0}^n {}_nC_k x^k$

両辺を $x$ で微分すると

$n(1+x)^{n-1} = \sum_{k=1}^n {}_nC_k k x^{k-1}$

$x=1$ を代入すると

$n(1+1)^{n-1} = \sum_{k=1}^n {}_nC_k k$

$n 2^{n-1} = \sum_{k=1}^n k \cdot {}_nC_k$

問題の式は、この式において $n=10$ の場合である。

したがって、$10 \cdot 2^{10-1} = 10 \cdot 2^9 = 10 \cdot 512 = 5120$

3. 最終的な答え

(1) 3

(2) 40

(3) 5120