上級者
数学A：整数
-
ヒント：整数問題の基本的な考え方は，よく分からなかったら具体的に値を入れて確認する．その後，この問題については，1．数学的帰納法により確認．2．二項定理を使って，必要な倍数でくくる．3．合同式\(\bmod\)で計算する． ただ，意識するのはやはり，倍数，余り\(\bmod\)である．
問題
\(a_{n}=3^{4n}13^{n}+(-1)^{n-1}2^{5n}\)の公約数を求めろ．あなたが選んだ公約数をこの問題のあなたの得点とする．(オリジナル)
解答
\(n=2\)を代入すると，\(a_{2}=1107785=5\times 7\times 31\times 1021\)
よって公約数の候補としては，\((5,7,31,35,155,217,1085)\)が考えられる．
次に，\(a_{n}=81^{n}13^{n}+(-1)^{n-1}32^{n}=1053^{n}+(-1)^{n-1}32^{n}\)
ここで，\(\bmod 31\)を考えると，\(1053=31\times 34-1\equiv -1\) \(\pmod{31}\)
\(32=31\times 1 +1\equiv 1\) \(\pmod{31}\)
よって\(a_{n}\equiv (-1)^n+(-1)^{n-1}=0\) \(\pmod{31}\)なので，\(a_{n}\)は31で割り切れる．
次に，\(\bmod 7\)を考えると，\(1053=7\times 150+3\equiv 3\) \(\pmod 7\)
\(32=7\times 5 -3\equiv -3\) \(\pmod 7\)
よって，\(a_{n}\equiv 3^n+(-1)^{n-1}(-3)^{n}=0\) \(\pmod 7\)なので，\(a_{n}\)は7で割り切れる．
次に，\(\bmod 5\)を考えると，\(1053=5\times 210+3\equiv 3\) \(\pmod 5\)
\(32=5\times 7 -3\equiv -3\) \(\pmod 5\)
よって，\(a_{n}\equiv 3^n+(-1)^{n-1}(-3)^{n}=0\) \(\pmod 5\)なので，\(a_{n}\)は5で割り切れる．
よって，\(a_{n}\)の最大公約数は\(5\times 7 \times 31=1085\)なので，私の得点を1085点とさせてください．
参考入試問題
整数\(a_{n}＝19^{n}＋(－1)^{n-1}2^{4n-3}\)のすべてを割り切る素数を求めよ．（86 東工大）
具体的に値を入れてみると，
\(a_{1}=21=3\times 7\)
\(a_{2}=329=47\times 7\)
よって，割り切る素数は7の可能性がある．
１．数学的帰納法による証明
\(a_{n}=19^{n}＋(－1)^{n-1}2^{4n-3}\)が7の倍数であると仮定すると，
\(a_{n+1}=19^{n+1}＋(－1)^{n}2^{4n+1}\)\(=19\times 19^{n}＋(－1)^{n}2^{4n+1}\)\(=19\times (a_{n}-(－1)^{n-1}2^{4n-3})＋(－1)^{n}2^{4n+1}\)\(=19a_{n}+(－1)^{n}(19\times 2^{4n-3}+16\times 2^{4n-3})\)\(=19a_{n}+(－1)^{n}\times 35\times 2^{4n-3}\)
\(a_{n}\)は7の倍数，\((－1)^{n}\times 35\times 2^{4n-3}\)は7の倍数．よって，\(a_{n+1}\)も7の倍数．
２．二項定理の使用
\(19^{n}=(21-2)^{n}\)\(=\displaystyle \sum_{i=0}^{n-1}{}_nC_{i}21^{n-i}(-2)^i+(-2)^{n}\)\(=21A+(-2)^{n}\)
\((－1)^{n-1}2^{4n-3}\)\(=(－1)^{n-1}2^{4(n-1)+1}=2(－1)^{n-1}16^{n-1}\)\(=2(－1)^{n-1}(14+2)^{n-1}\)\(=\cdots=14B+2(-2)^{n-1}\)
よって，\(a_{n}＝19^{n}＋(－1)^{n-1}2^{4n-3}\)\(=21A+14B+(-2)^{n}+2(-2)^{n-1}\)\(=7(3A+2B)\)
よって，全てを割り切る素数は7