整数の性質の問題

以下、合同式はすべて $7$ を法とする。

$3^n$ の余り

$3^1\equiv 3,3^2\equiv 2,3^3\equiv 6,3^4\equiv 4,3^5\equiv 5,3^6\equiv 1$ である。$3^6\equiv 1$ より、$3^n$ を $7$ で割った余りは $n$ を $6$ で割った余りだけで決まる。

$n^2$ の余り

$n\equiv 0,1,2,3,4,5,6$ に対して、$n^2\equiv 0,1,4,2,2,4,1$ である。$n^2$ の余りは $n$ を $7$ で割った余りだけで決まり、とりうる値は $0,1,2,4$ のみである。

条件の整理

$3^n+n^2\equiv 0$ すなわち $n^2\equiv -3^n$ となる条件を、$n$ を $6$ で割った余りで場合分けして調べる。

• $n\equiv 1(\mathrm{mod}6)$：$-3^n\equiv -3\equiv 4$。$n^2\equiv 4$ より $n\equiv 2,5(\mathrm{mod}7)$。
• $n\equiv 2(\mathrm{mod}6)$：$-3^n\equiv -2\equiv 5$。$n^2\equiv 5$ となる $n$ はない。
• $n\equiv 3(\mathrm{mod}6)$：$-3^n\equiv -6\equiv 1$。$n^2\equiv 1$ より $n\equiv 1,6(\mathrm{mod}7)$。
• $n\equiv 4(\mathrm{mod}6)$：$-3^n\equiv -4\equiv 3$。$n^2\equiv 3$ となる $n$ はない。
• $n\equiv 5(\mathrm{mod}6)$：$-3^n\equiv -5\equiv 2$。$n^2\equiv 2$ より $n\equiv 3,4(\mathrm{mod}7)$。
• $n\equiv 0(\mathrm{mod}6)$：$-3^n\equiv -1\equiv 6$。$n^2\equiv 6$ となる $n$ はない。

$42$ を法とする余りへの書き直し

$6$ と $7$ は互いに素なので、条件は $n$ を $42$ で割った余りで表せる。$n=6k+r$ とおいて $k$ を求める。$6\equiv -1(\mathrm{mod}7)$ であることを使う。

• $n\equiv 1(\mathrm{mod}6)$ かつ $n\equiv 2(\mathrm{mod}7)$：$1+6k\equiv 2$ より $-k\equiv 1$、よって $k\equiv 6$。したがって $n\equiv 37$。
• $n\equiv 1(\mathrm{mod}6)$ かつ $n\equiv 5(\mathrm{mod}7)$：$-k\equiv 4$ より $k\equiv 3$。したがって $n\equiv 19$。
• $n\equiv 3(\mathrm{mod}6)$ かつ $n\equiv 1(\mathrm{mod}7)$：$3+6k\equiv 1$ より $-k\equiv -2$、よって $k\equiv 2$。したがって $n\equiv 15$。
• $n\equiv 3(\mathrm{mod}6)$ かつ $n\equiv 6(\mathrm{mod}7)$：$-k\equiv 3$ より $k\equiv 4$。したがって $n\equiv 27$。
• $n\equiv 5(\mathrm{mod}6)$ かつ $n\equiv 3(\mathrm{mod}7)$：$5+6k\equiv 3$ より $-k\equiv -2$、よって $k\equiv 2$。したがって $n\equiv 17$。
• $n\equiv 5(\mathrm{mod}6)$ かつ $n\equiv 4(\mathrm{mod}7)$：$-k\equiv -1$ より $k\equiv 1$。したがって $n\equiv 11$。

よって条件は、$n$ を $42$ で割った余りが $11,15,17,19,27,37$ のいずれかであることと同値である。

（確認：$n=11$ のとき $3^{11}\equiv 3^5\equiv 5$、$11^2=121\equiv 2$ で、和は $7\equiv 0$ となる。）

個数を数える

$1000=42\times 23+34$ である。

• $1\leqq n\leqq 966$ には、$42$ 個ずつの区切りが $23$ 組あり、各組に $6$ 個ずつ条件を満たす $n$ がある。よって $23\times 6=138$ 個。
• $967\leqq n\leqq 1000$ では、$42$ で割った余りが $1$ から $34$ までとなる。このうち条件を満たす余りは $11,15,17,19,27$ の $5$ 個。

したがって、求める個数は $138+5=143$ 個である。

$3^n\mathrm{mod}7$ の周期は 6、$n^2\mathrm{mod}7$ の周期は 7 なので、条件は $n\mathrm{mod}42$ で決まる。

$n\mathrm{mod}6=r$ ごとに $3^n\mathrm{mod}7$ は $r=0,1,2,3,4,5$ の順に $1,3,2,6,4,5$ となる。したがって $n^2\equiv -3^n(\mathrm{mod}7)$ を満たすべき右辺は順に $6,4,5,1,3,2$ である。

平方数の $7$ での余りは $0,1,2,4$ のみで、$n\mathrm{mod}7=s$ とすると $s=0,1,2,3,4,5,6$ に対し $n^2\mathrm{mod}7=0,1,4,2,2,4,1$ となる。

よって右辺が $0,1,2,4$ のいずれかになる場合だけ解がある。
- $r=1$（右辺 $4$）: $s=2,5$
- $r=3$（右辺 $1$）: $s=1,6$
- $r=5$（右辺 $2$）: $s=3,4$

それ以外の $r=0,2,4$ では右辺が平方数の余りにならず解なし。

中国剰余定理で $n\mathrm{mod}42$ を求めると $11,15,17,19,27,37$ の 6 個になる。確認として $n=11$ では $3^{11}=177147$、$177147\mathrm{mod}7=5$、$n^2=121\equiv 2$ で和は $7$ の倍数になる。

$1000=42\cdot 23+34$ なので、$1\sim 966$ には $23$ 周期分で $23\cdot 6=138$ 個ある。残りの $967\sim 1000$ は剰余 $1\sim 34$ に対応し、このうち $11,15,17,19,27$ の $5$ 個が該当する。

合計は $138+5=143$ 個。