整数論の問題

$35=5\cdot 7$ であり、$5$ と $7$ は互いに素なので、与えられた合同式は次の 2 つの合同式を同時にみたすことと同値である。
$$2^n\equiv n(\mathrm{mod}5),2^n\equiv n(\mathrm{mod}7).$$

法 $5$ の条件　$2^4=16\equiv 1(\mathrm{mod}5)$ であり、$2,2^2,2^3\not\equiv 1$ なので、法 $5$ での $2$ の位数は $4$ である。よって $2^n\mathrm{mod}5$ は $n\mathrm{mod}4$ で決まる。
- $n\equiv 0(\mathrm{mod}4)$：$2^n\equiv 1$、条件は $n\equiv 1(\mathrm{mod}5)$。CRT より $n\equiv 16(\mathrm{mod}20)$。
- $n\equiv 1(\mathrm{mod}4)$：$2^n\equiv 2$、条件は $n\equiv 2(\mathrm{mod}5)$。$n\equiv 17(\mathrm{mod}20)$。
- $n\equiv 2(\mathrm{mod}4)$：$2^n\equiv 4$、条件は $n\equiv 4(\mathrm{mod}5)$。$n\equiv 14(\mathrm{mod}20)$。
- $n\equiv 3(\mathrm{mod}4)$：$2^n\equiv 3$、条件は $n\equiv 3(\mathrm{mod}5)$。$n\equiv 3(\mathrm{mod}20)$。

よって法 $5$ の条件は $n\equiv 3,14,16,17(\mathrm{mod}20)$ と同値である。

法 $7$ の条件　$2^3=8\equiv 1(\mathrm{mod}7)$ なので位数は $3$。
- $n\equiv 0(\mathrm{mod}3)$：$2^n\equiv 1$、$n\equiv 1(\mathrm{mod}7)$ より $n\equiv 15(\mathrm{mod}21)$。
- $n\equiv 1(\mathrm{mod}3)$：$2^n\equiv 2$、$n\equiv 2(\mathrm{mod}7)$ より $n\equiv 16(\mathrm{mod}21)$。
- $n\equiv 2(\mathrm{mod}3)$：$2^n\equiv 4$、$n\equiv 4(\mathrm{mod}7)$ より $n\equiv 11(\mathrm{mod}21)$。

よって法 $7$ の条件は $n\equiv 11,15,16(\mathrm{mod}21)$ と同値である。

組み合わせ　$\gcd (20,21)=1$ なので、中国剰余定理により $n\equiv r(\mathrm{mod}20)$, $n\equiv s(\mathrm{mod}21)$ をみたす $n$ は法 $420$ でただ 1 つ定まる。$n=r+20k$ とおくと $20\equiv -1(\mathrm{mod}21)$ より $r-k\equiv s$、すなわち $k\equiv r-s(\mathrm{mod}21)$（$0\leqq k\leqq 20$）。

これら $12$ 個はすべて $1$ 以上 $420$ 以下にあり、$1\leqq n\leqq 420$ の解はちょうどこれらである（例：$n=16$ のとき $2^{16}=65536=35\cdot 1872+16$ で確かに成り立つ）。

和は
$$(263+183+163)+(74+414+394)+(116+36+16)+(137+57+37)=609+882+168+231=1890.$$

（検算：和を $20$ で割った余りは $3(3+14+16+17)=150\equiv 10$、$21$ で割った余りは $4(11+15+16)=168\equiv 0$ となり、$1890$ と一致する。）

答えは $1890$ である。

$35=5\cdot 7$ であり、2 は 35 と互いに素である。$2$ の位数は mod 5 で 4、mod 7 で 3 なので、$2^{12}\equiv 1(\mathrm{mod}35)$ となる。よって $2^n\mathrm{mod}35$ は周期 12 で、$n\equiv r(\mathrm{mod}12)$ のとき $2^n\equiv 2^r$ である。

したがって条件は $n\equiv 2^r(\mathrm{mod}35)$ かつ $n\equiv r(\mathrm{mod}12)$ と書ける。ここで $r=0,1,\dots ,11$ とする。$\gcd (35,12)=1$ なので中国剰余定理により、$r$ ごとに $1\le n\le 420$ の範囲でちょうど 1 つの解が決まる。

$2^r\mathrm{mod}35$ ($r=0,\dots ,11$) は 1, 2, 4, 8, 16, 32, 29, 23, 11, 22, 9, 18 である。

$a=2^r\mathrm{mod}35$ とおき、$n=a+35k$ ($0\le k\le 11$) とする。$35\equiv -1(\mathrm{mod}12)$ より $k\equiv a-r(\mathrm{mod}12)$ となる。各 $r$ について解を求めると次のとおり。

• $r=0$: $n=36$
• $r=1$: $n=37$
• $r=2$: $n=74$
• $r=3$: $n=183$
• $r=4$: $n=16$
• $r=5$: $n=137$
• $r=6$: $n=414$
• $r=7$: $n=163$
• $r=8$: $n=116$
• $r=9$: $n=57$
• $r=10$: $n=394$
• $r=11$: $n=263$

検算として $n=16$ を確かめる。$2^{16}=2^{12}\cdot 2^4\equiv 16(\mathrm{mod}35)$ であり、$n=16$ と一致する。ほかの解も $n\mathrm{mod}12=r$、$n\mathrm{mod}35=a$ を確認した。

和は $36+37+74+183+16+137+414+163+116+57+394+263=1890$。