創作整数問題#73解法＆創作整数問題#74

解答例

求める素数を$p$と置く。$a_1=1241$ より、$p$は$1241$の素因数として現れる。$1241<36^2=1296$ となるので、$35$以下の素数で$1241$を割り切るものを探していくと$17$が見つかり、$$1241=17 \cdot 73$$と素因数分解できることが分かる。したがって、素数$p$の値としてあり得るものは $17$ または $73$ である。

ここで $a_2=63145$ である。これは$73$で割り切れるが、$17$では割り切れない。よって $p=73$ の場合に限られる。

以下、任意の正の整数$n$に対して$a_{n}$が$73$で割り切れることを示す。

 ①数学的帰納法による証明

$n=1$ のとき $a_1=17 \cdot 73$ より、$a_n$は$73$で割り切れる。

$n=i$（$i=2,3,4,\cdots$）のとき$a_i$が$73$で割り切れると仮定する。$a_{i+1}$の式を変形すると$$\begin{aligned} & \quad \, \, 8^{(i+1)+2}+9^{2(i+1)+1} \\ &=8 \cdot 8^{i+2}+81(9^{2i+1}) \\ &= 8 \cdot 8^{i+2}+81(a_i-8^{i+2}) \\ & \quad \quad \quad (\because a_i=8^{i+2}+9^{2i+1}) \\ &= 81a_i-73 \cdot 8^{i+2} \end{aligned}$$となる。仮定より、$a_i$は$73$で割り切れるから、$$a_{i+1}=8^{(i+1)+2}+9^{2(i+1)+1}$$も$73$で割り切れる。故に $n=i+1$ でも成立する。

以上より、数学的帰納法から任意の正の整数$n$に対して$a_{n}$が$73$で割り切れることが示された。したがって、求める素数$p$は$$\color{red}{73}$$である。

②合同式による証明

$$\begin{aligned} a_n &= 8^{n+2}+9^{2n+1} \\ &=64 \cdot 8^n+9 \cdot 81^n \\ &\equiv (-9) \cdot 8^n+9 \cdot 8^n \pmod{73} \\ &= 0 \end{aligned}$$より、$a_n$は$n$の値によらず$$a_n \equiv 0 \pmod{73}$$を満たすから、任意の正の整数$n$に対して$a_{n}$が$73$で割り切れることが示された。したがって、求める素数$p$は$$\color{red}{73}$$である。