倍数の問題　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　自然数 ｎ を含む数の倍数問題は、毎年どこかの大学で出題される頻出問題である。

たとえば、　ｎ が自然数であるとき、

　ｎ⁴＋２ｎ³＋１１ｎ²＋１０ｎ　は２４の倍数であることを証明せよ。

というタイプの問題である。

　このような問題の特徴は、それまで学んだことを生かして、各個人の独創的なアイデアが
求められるという点であろう。それ故に、受験生泣かせでもある。

　ただ、基本的な解法は広く知れ渡り、特に、いくつかの具体例から法則性を学び、それを
数学的帰納法で示すという流れが多いので、安心してよいと思う。

　十分高校数学的で数学的な論述を見る問題として適切であり、また受験生個々の数学力
が如実に表れるので、それが入試問題として好まれる理由だろう。

　上述の問題を解いてみよう。ボーッと眺めていても問題は解けない。次のような式変形が
ポイントだろう。これは、高校で学ぶ「連続する２整数の積は偶数」ということを意識している。

（解）　ｎ⁴＋２ｎ³＋１１ｎ²＋１０ｎ

　＝ｎ（ｎ³＋２ｎ²＋１１ｎ＋１０）＝ｎ（ｎ＋１）（ｎ²＋ｎ＋１０）＝ｎ（ｎ＋１）｛（ｎ＋２）（ｎ−１）＋１２｝

　＝（ｎ−１）ｎ（ｎ＋１）（ｎ＋２）＋１２ｎ（ｎ＋１）

　ｎ（ｎ＋１）は連続する２整数の積で、２の倍数より、１２ｎ（ｎ＋１）は２４の倍数である。

　（ｎ−１）ｎ（ｎ＋１）（ｎ＋２）＝４！・_ｎ+2Ｃ₄＝２４・_ｎ+2Ｃ₄　より、２４の倍数である。

よって、ｎ⁴＋２ｎ³＋１１ｎ²＋１０ｎ　は、２４の倍数である。　　（終）


　数学的帰納法による証明も考えられるが、式変形や用いられる理論は上記とほとんど同
様である。

　いくつか別な例題を見ていこう。
（これらの問題は当ＨＰがいつもお世話になっているＳ（Ｈ）さんよりご紹介いただきました。）


名古屋市大（１９８２年）

ｎ を自然数とするとき、　３^ｎ+1＋４^2ｎ-1 は１３で割り切れることを証明せよ。

（解）　ｎ＝１　のとき、　３^ｎ+1＋４^2ｎ-1＝９＋４＝１３　は明らかに１３で割り切れる。

　ｎ＝ｋ（ｋ≧１）のとき、成り立つと仮定する。すなわち、３^ｋ+1＋４^2ｋ-1 は１３で割り切れる。

このとき、　３^ｋ+1＋４^2ｋ-1 ＝１３ｍ　（ｍは自然数）　とおける。

ｎ＝ｋ＋１　のとき、

　３^ｋ+2＋４^2ｋ+1＝３・３^ｋ+1＋１６・４^2ｋ-1＝３・（１３ｍ−４^2ｋ-1）＋１６・４^2ｋ-1

＝１３（３ｍ＋４^2ｋ-1）　より、１３で割り切れる。

　よって、ｎ＝ｋ＋１　のときも成り立つ。

したがって、すべての自然数 ｎ に対して、　３^ｎ+1＋４^2ｎ-1 は１３で割り切れる。　　（終）


　平成２１年３月２１日付けで、ＨＮ「ｚｋ４３」さんから、数学的帰納法に依らない証明をいた
だいた。

（別解）　Ｆ（ｎ）＝３^ｎ+1＋４^2ｎ-1　とおくと、Ｆ（ｎ＋３）＝３^ｎ+4＋４^2ｎ+5＝２７・３^ｎ+1＋６４²・４^2ｎ-1

　ここで、　２７≡１　（ｍｏｄ　１３）　、　６４²≡（−１）²＝１　（ｍｏｄ　１３）　より、

　Ｆ（ｎ＋３）≡Ｆ（ｎ）　（ｍｏｄ　１３）

よって、題意を満たすためには、Ｆ（１）、Ｆ（２）、Ｆ（３） について調べれば十分である。

　Ｆ（１）＝９＋４＝１３≡０　（ｍｏｄ　１３）　、　Ｆ（２）＝２７＋６４＝９１≡０　（ｍｏｄ　１３）

　Ｆ（３）＝８１＋１０２４＝１１０５≡０　（ｍｏｄ　１３）

以上から、すべての自然数 ｎ に対して、　３^ｎ+1＋４^2ｎ-1 は１３で割り切れる。　　（終）


　また、ｚｋ４３さんは、剰余について新しい視座を見出された。

すなわち、　３^ｎ ： ３ 、９ 、２７ 、８１ 、２４３ 、７２９ 、・・・　において、１３を法とすれば、

　３^ｎ ： ３ 、９ 、１ 、３ 、９ 、１ 、・・・　と、「３ 、９ 、１」が循環する。同様に、

　４^ｎ ： ４ 、１６ 、６４ 、２５６ 、１０２４ 、４０９６ 、１６３８４ 、・・・　において、

１３を法とすれば、　４^ｎ ： ４ 、３ 、１２ 、９ 、１０ 、１ 、４ 、・・・　と、

「４ 、１３ 、１２ 、９ 、１０ 、１」が循環する。このとき、

なので、すべての自然数 ｎ に対して、　３^ｎ+1＋４^2ｎ-1 が１３で割り切れることは十分予想
できる。


（コメント）　今まで経験のない視座に感動しました！ｚｋ４３さんに感謝します。


東京工業大（１９８６年）

　整数 ａ_ｎ＝１９^ｎ＋（−１）^ｎ-1２^4ｎ-3 （ｎ＝１、２、３、・・・）のすべてを割り切る素数を
求めよ。

（解）　ｎ＝１　のとき、　ａ₁＝１９^ｎ＋（−１）^ｎ-1２^4ｎ-3＝１９＋２＝２１＝３・７

　ｎ＝２　のとき、　ａ₂＝１９^ｎ＋（−１）^ｎ-1２^4ｎ-3＝３６１−３２＝３２９＝７・４７

よって、　ａ_ｎ　のすべてを割り切る素数は、７であることが類推できる。

　この類推が正しいことを、数学的帰納法により示す。

ｎ＝１　のとき、ａ₁＝１９^ｎ＋（−１）^ｎ-1２^4ｎ-3＝１９＋２＝２１　は明らかに７の倍数である。

ｎ＝ｋ（ｋ≧１）のとき成り立つと仮定する。即ち、ａ_ｋ＝１９^ｋ＋（−１）^ｋ-1２^4ｋ-3　は７の倍数。

　このとき、　１９^ｋ＋（−１）^ｋ-1２^4ｋ-3＝７ｍ　（ｍは自然数）　とおける。

ｎ＝ｋ＋１　のとき、

　ａ_ｋ+1＝１９^ｋ+1＋（−１）^ｋ２^4ｋ+1＝１９・１９^ｋ−１６・（−１）^ｋ-1２^4ｋ-3

　＝１９・（７ｍ−（−１）^ｋ-1２^4ｋ-3）−１６・（−１）^ｋ-1２^4ｋ-3

　＝７（１９ｍ−５（−１）^ｋ-1２^4ｋ-3）　より、７の倍数。

　よって、ｎ＝ｋ＋１　のときも成り立つ。

したがって、すべての正の整数 ｎ に対して、１９^ｎ＋（−１）^ｎ-1２^4ｎ-3 は７の倍数である。

すなわち、　１９^ｎ＋（−１）^ｎ-1２^4ｎ-3　のすべてを割り切る素数は、７である。　　（終）


（コメント）　一度、数学的帰納法の証明に慣れてしまうと、両者は全く機械的に行うことが
　　　　　　でき、あまり面白さは感じられない。


　直接的に、例えば、　３^ｎ+1＋４^2ｎ-1＝１３Ｆ（ｎ）　となるＦ（ｎ）を見いだすことは可能だろう
か？Ｓ（Ｈ）さんは、こちらの方法に関心を持たれているようだ。

　Ｓ（Ｈ）さんによれば、Ｆ（ｎ）＝（1/52）（３６・３^ｎ-1＋１６・１６^ｎ-1）　と書けるらしい。


　平成２１年３月２２日付けで、ｚｋ４３さんが、（２）について合同式を利用する解法を示され
たので紹介したい。

（別解）　ｎ＝１　のとき、　ａ₁＝１９^ｎ＋（−１）^ｎ-1２^4ｎ-3＝１９＋２＝２１＝３・７

　ｎ＝２　のとき、　ａ₂＝１９^ｎ＋（−１）^ｎ-1２^4ｎ-3＝３６１−３２＝３２９＝７・４７

よって、　ａ_ｎ　のすべてを割り切る素数は、７であることが類推できる。

　このとき、すべての正の整数 ｎ に対して、７を法として考えると、

　ａ_ｎ＝１９^ｎ＋（−１）^ｎ-1２^4ｎ-3　において、１９^ｎ≡（−２）^ｎ　（ｍｏｄ　７）

　（−１）^ｎ-1２^4ｎ-3＝（−１）^ｎ-1２^4ｎ-4・２＝（−１）^ｎ-1１６^ｎ-1・２≡（−１）^ｎ-1２^ｎ-1・２　（ｍｏｄ　７）

　≡−（−２）^ｎ　（ｍｏｄ　７）

よって、　ａ_ｎ≡（−２）^ｎ−（−２）^ｎ＝０　（ｍｏｄ　７）　　（終）


　また、ｚｋ４３さんは、「ｎ が奇数のとき、ａ_ｎ≡０　（ｍｏｄ　３）」であることも示された。

すなわち、ｎ が奇数のとき、　ａ_ｎ＝１９^ｎ＋（−１）^ｎ-1２^4ｎ-3≡１＋（−１）^ｎ＝０　（ｍｏｄ　３）


　次の　静岡大学　前期　理系（２００９）　の（１）は、確実に、名古屋市大（１９８２）の問
題に類似している。さらに、（２）は、京都大学　理系（２００３） の問題を意識しているように
感じる。


次の問いに答えよ。

（１）　すべての自然数 ｎ に対して、４^ｎ+1＋５^2ｎ-1 は２１で割り切れることを証明せよ。

（２）　次の条件を満たす定数でない多項式 Ｆ（ｘ） を推定し、その推定が正しいことを
　　証明せよ。

　（ａ）　Ｆ（４）＝２１

　（ｂ）　すべての自然数 ｎ に対して、ｘ^ｎ+1＋（ｘ＋１）^2ｎ-1 は Ｆ（ｘ） で割り切れる。

（解）（１）　ｎ＝１　のとき、　４^ｎ+1＋５^2ｎ-1＝１６＋５＝２１　は２１で割り切れる。

　ｎ＝ｋ（ｋ≧１）のとき、成り立つと仮定する。すなわち、４^ｋ+1＋５^2ｋ-1 は２１で割り切れる。

　このとき、　４^ｋ+1＋５^2ｋ-1 ＝２１ｍ　（ｍは自然数）　とおける。

　ｎ＝ｋ＋１　のとき、

　４^ｋ+2＋５^2ｋ+1＝４・４^ｋ+1＋２５・５^2ｋ-1＝４・（２１ｍ−５^2ｋ-1）＋２５・５^2ｋ-1

＝２１（４ｍ＋５^2ｋ-1）　より、２１で割り切れる。

　よって、ｎ＝ｋ＋１　のときも成り立つ。

したがって、すべての自然数 ｎ に対して、　４^ｎ+1＋５^2ｎ-1 は２１で割り切れる。

（２）　Ｇ_ｎ（ｘ）＝ｘ^ｎ+1＋（ｘ＋１）^2ｎ-1　とおくと、

　Ｇ₁（ｘ）＝ｘ²＋ｘ＋１ で、Ｇ₁（４）＝２１　より、　Ｆ（ｘ）＝ｘ²＋ｘ＋１　と推定する。この推定が

正しいことを、数学的帰納法により示す。

　ｎ＝１　のとき、明らかに成り立つ。

　ｎ＝ｋ（ｋ≧１）のとき、成り立つと仮定する。

　すなわち、Ｆ（４）＝２１　で、Ｇ_ｋ（ｘ） はＦ（ｘ）で割り切れるので、

　　Ｇ_ｋ（ｘ） ＝Ｆ（ｘ）Ｑ（ｘ）　（Ｑ（ｘ）は多項式）

このとき、

　Ｇ_ｋ+1（ｘ）＝ｘ^ｋ+2＋（ｘ＋１）^2ｋ+1＝ｘ^ｋ+2＋（ｘ＋１）²（Ｆ（ｘ）Ｑ（ｘ）−ｘ^ｋ+1）

　＝−ｘ^ｋ+1（ｘ²＋ｘ＋１）＋（ｘ＋１）²Ｆ（ｘ）Ｑ（ｘ）

　＝Ｆ（ｘ）（−ｘ^ｋ+1＋（ｘ＋１）²Ｑ（ｘ））　より、Ｆ（ｘ）で割り切れる。

よって、ｎ＝ｋ＋１　のときも成り立つ。

したがって、すべての自然数 ｎ に対して、ｘ^ｎ+1＋（ｘ＋１）^2ｎ-1 は Ｆ（ｘ） で割り切れることが

示された。以上から、推定は正しく、　Ｆ（ｘ）＝ｘ²＋ｘ＋１　である。　　（終）


（コメント）　この問いは「数学的帰納法で」という限定条件が付いているが、直接的な証明も
　　　　　　可能である。

　Ｇ_ｎ（ｘ）＝ｘ^ｎ+1＋（ｘ＋１）^2ｎ-1　が、Ｆ（ｘ）＝ｘ²＋ｘ＋１　で割り切れることを、次のように計
算しても分かる。

　Ｆ（ｘ）＝ｘ²＋ｘ＋１＝（ｘ−ω）（ｘ−ω²）　なので、Ｇ_ｎ（ｘ）がＦ（ｘ）で割り切れることを示すに

は、Ｇ_ｎ（ω）＝０　、Ｇ_ｎ（ω²）＝０　であることを示せば十分である。
（→　参考 ： 「オメガ（ω）の真実」）

　Ｇ_ｎ（ω）＝ω^ｎ+1＋（ω＋１）^2ｎ-1＝ω^ｎ+1＋（−ω²）^2ｎ-1＝ω^ｎ+1−ω^4ｎ-2＝ω^ｎ+1−ω^ｎ-2

＝ω^ｎ-2（ω³−１）＝０

　Ｇ_ｎ（ω²）＝ω^2ｎ+2＋（ω²＋１）^2ｎ-1＝ω^2ｎ+2＋（−ω）^2ｎ-1＝ω^2ｎ+2−ω^2ｎ-1

＝ω^2ｎ-1（ω³−１）＝０

　以上から、　Ｇ_ｎ（ｘ）＝ｘ^ｎ+1＋（ｘ＋１）^2ｎ-1　は、Ｆ（ｘ）＝ｘ²＋ｘ＋１　で割り切れる。

　よって、Ｆ（ｘ）＝ｘ²＋ｘ＋１　が求める多項式である。　　（終）


京都大学　文系（２００１年）

　任意の整数 ｎ に対し、 ｎ⁹−ｎ³ は９で割り切れることを示せ。

（解）　ｎ⁹−ｎ³＝ｎ³（ｎ⁶−１）＝（ｎ³−１）ｎ³（ｎ³＋１）

　ここで、　ｎ＝３ｍ　（ｍは整数）　のとき、　ｎ³＝２７ｍ³　なので、９で割り切れる。

　ｎ＝３ｍ＋１　（ｍは整数）のとき、ｎ³−１＝２７ｍ³＋２７ｍ²＋９ｍ　なので、９で割り切れる。

　ｎ＝３ｍ＋２　（ｍは整数）のとき、ｎ³＋１＝２７ｍ³＋５４ｍ²＋３６ｍ＋９　なので、９で割り

　切れる。

　以上から、任意の整数 ｎ に対し、 ｎ⁹−ｎ³ は９で割り切れる。　　（終）


（コメント）　ちょっと、問題が易しすぎるような．．．？


　当ＨＰがいつもお世話になっている「ｚｋ４３」さんから別解を頂いた。（平成２１年４月１３日付け）

（別解）　ｎ が３で割り切れなければ、オイラーの定理から、　ｎ⁶≡１　（ｍｏｄ　９）

　よって、この場合、ｎ⁹−ｎ³＝ｎ³（ｎ⁶−１） は、９で割り切れる。

　ｎ が３で割り切れれば、ｎ³ は、９で割り切れる。

　よって、この場合、ｎ⁹−ｎ³＝ｎ³（ｎ⁶−１） は、９で割り切れる。

　以上から、任意の整数 ｎ に対し、 ｎ⁹−ｎ³ は９で割り切れる。　　（終）


　「ｚｋ４３」さんによれば、上記の証明を鑑みて、「ｎ⁸−ｎ² は９で割り切れる。」という問題も
作れるとのこと。

　また、「奇数の平方は、８で割ると１余るという事実を一般化して、

　　奇数の２ⁿ乗は、２ⁿ⁺²で割ると、１余る

ということも成り立ち、結構面白いとのこと。これから、ｍｏｄ ２ⁿ⁺² での既約剰余類群は巡回
群にはならないことが分かるそうである。ｚｋ４３さんに感謝します。


　また、平成２１年４月１３日付けで、Ｓ（Ｈ）さんより、次のような別解をご教示いただいた。

　まず、次の定理を用いる。これは、１９９３年度前期の東京工業大学の入試問題である。

　（この手の問題は受験生には厳しい難問で、解答に「帰納法で示す」と書いただけで、満点の３０点
　　中１０点が貰えたという噂が．．．？）

定　理　　ｎ を自然数、Ｐ（ｘ）を ｎ 次の多項式とする。

　Ｐ（０）、Ｐ（１）、・・・、Ｐ（ｎ）が整数ならば、すべての整数 ｋ に対し、Ｐ（ｋ）は整数で

ある。

　わずかに ｎ＋１ 個の値の様子から、すべての値の様子が分かってしまうという末恐ろし
い事実ですね！

　「整数値多項式」ということを意識すれば、次のような証明が考えられるだろう。

（証明）　ｎ 次の多項式 Ｐ（ｘ） が、

　Ｐ（ｘ）＝ａ＋ｂｘ＋(ｃ/2!)ｘ（ｘ−１）＋・・・＋(ｄ/ｎ!)ｘ（ｘ−１）・・・（ｘ−ｎ＋１）

　即ち、整数値多項式　Ｆｋ(Ｘ）＝Ｘ(Ｘ−１)(Ｘ−２)(Ｘ−３)・・・(Ｘ−ｋ＋１)／ｋ！を用いて、

　Ｐ（ｘ）＝ａ＋ｂ・Ｆ1(Ｘ）＋ｃ・Ｆ2(Ｘ）＋・・・＋ｄ・Ｆｎ(Ｘ）

の形に書けることを数学的帰納法で示す。

　ｎ＝１　のときは、明らかに成り立つ。

　ｎ＝ｋ（ｋ≧１）のとき成り立つと仮定する。

　ｎ＝ｋ＋１　のとき、　Ｐ（ｘ）は、ｋ＋１次の多項式で、その最高次の係数をＡとすれば、

　　Ｐ（ｘ）−Ａｘ（ｘ−１）・・・（ｘ−ｋ）　は、ｋ次の多項式となる。

　帰納法の仮定により、

　　Ｐ（ｘ）−Ａｘ（ｘ−１）・・・（ｘ−ｋ）＝ａ＋ｂ・Ｆ1(Ｘ）＋ｃ・Ｆ2(Ｘ）＋・・・＋ｄ・Ｆｋ(Ｘ）

と書ける。そこで、ｅ＝Ａ・（ｋ＋１）！とおけば、

　　Ｐ（ｘ）＝ａ＋ｂ・Ｆ1(Ｘ）＋ｃ・Ｆ2(Ｘ）＋・・・＋ｄ・Ｆｋ(Ｘ）＋ｅ・Ｆｋ+1(Ｘ）

と書けることが示された。よって、ｎ＝ｋ＋１のときも成り立つ。

　以上から、すべての自然数 ｎ について、ｎ 次の多項式 Ｐ（ｘ） は、

　Ｐ（ｘ）＝ａ＋ｂ・Ｆ1(Ｘ）＋ｃ・Ｆ2(Ｘ）＋・・・＋ｄ・Ｆｎ(Ｘ）

の形に書ける。

　題意より、Ｐ（０）、Ｐ（１）、・・・、Ｐ（ｎ）が整数なので、

　　ａ 、ａ＋ｂ 、ａ＋ｂ＋ｃ 、・・・ 、ａ＋ｂ＋ｃ＋ｄ

はすべて整数である。このとき、ａ 、ｂ 、ｃ 、・・・ 、ｄ　はすべて整数となる。

　したがって、すべての整数 ｘ に対して、整数値多項式　Ｆｋ(Ｘ）は整数値をとり、その係数

も整数なので、多項式 Ｐ（ｘ） は、整数値をとる。

　すなわち、すべての整数 ｋ に対し、Ｐ（ｋ）は整数である。　　（証終）


　１９９３年度前期の東京工業大学の入試問題と同様の問題が、１９９７年度 名古屋大学の
前期理系で出題されたことを、Ｓ（Ｈ）さんよりご教示いただいた。（平成２１年４月２３日付け）


名古屋大学　前期理系（１９９７年）　

（１）　多項式　Ｆ（ｘ）＝ｘ³＋ａｘ²＋ｂｘ＋ｃ　（ａ、ｂ、ｃ は実数）を考える。
　Ｆ（−１）、Ｆ（０）、Ｆ（１） がすべて整数ならば、すべての整数 ｎ に対し、Ｆ（ｎ）は整数である
ことを示せ。

（２）　Ｆ（１９９６）、Ｆ（１９９７）、Ｆ（１９９８） がすべて整数の場合はどうか？

（解）（１）　題意より、

　Ｆ（−１）＝−１＋ａ−ｂ＋ｃ　、Ｆ（０）＝ｃ　、Ｆ（１）＝１＋ａ＋ｂ＋ｃ　はすべて整数で、

　ａ＝｛ Ｆ（−１）−２Ｆ（０）＋Ｆ（１） ｝/２　、ｂ＝−｛ Ｆ（−１）＋２−Ｆ（１） ｝/２　、ｃ＝Ｆ（０）

　このとき、すべての整数 ｎ に対し、

　Ｆ（ｎ）＝ｎ³＋ａｎ²＋ｂｎ＋ｃ

　＝ｎ³＋｛ Ｆ（−１）−２Ｆ（０）＋Ｆ（１） ｝ｎ²/２−｛ Ｆ（−１）＋２−Ｆ（１） ｝ｎ/２＋Ｆ（０）

　＝ｎ³＋ Ｆ（−１）・ｎ（ｎ−１）/２−Ｆ（０）・（ｎ²−１）＋Ｆ（１）・ｎ（ｎ＋１）/２

　ここで、　ｎ（ｎ−１）/２　、ｎ（ｎ＋１）/２　は整数なので、すべての整数 ｎ に対し、Ｆ（ｎ）は整

数となる。

（２）　Ｇ（ｘ）＝Ｆ（ｘ＋１９９７）　とおくと、　Ｇ（ｘ）＝ｘ³＋ｐｘ²＋ｑｘ＋ｒ　（ｐ、ｑ、ｒ は実数）で、

　題意より、　Ｇ（−１）、Ｇ（０）、Ｇ（１） はすべて整数。

　よって、（１）より、　すべての整数 ｍ に対し、Ｇ（ｍ）＝Ｆ（ｍ＋１９９７）は整数となる。

　したがって、すべての整数 ｎ＝ｍ＋１９９７ に対し、Ｆ（ｎ）＝Ｆ（ｍ＋１９９７）＝Ｇ（ｍ）　は整

数となる。　　（終）


　上記の東京工業大学の定理を用いれば、京都大学の問題は、次のように解かれる。

（別解）　Ｐ（ｎ）＝（ｎ⁹−ｎ³）/９　とおく。

　このとき、　Ｐ（１）＝０　　、Ｐ（２）＝（５１２−８）/９＝５６　　、Ｐ（３）＝２１８４　、

　　Ｐ（４）＝２９１２０　　、Ｐ（５）＝２１７０００　　、Ｐ（６）＝１１１９７２０　、

　　Ｐ（７）＝４４８３６９６　　、Ｐ（８）＝１４９１３０２４　　、Ｐ（９）＝４３０４６６４０

　さらに、　Ｐ（０）＝０　なので、　Ｐ（０）、Ｐ（１）、・・・、Ｐ（９）はすべて整数となる。

　よって、定理により、すべての整数 ｎ　に対して、Ｐ（ｎ）は整数となる。

　したがって、任意の整数 ｎ に対し、 ｎ⁹−ｎ³ は９で割り切れる。　　（別解終）


（コメント）　この問題は、まさに整数値多項式の独壇場ですね！Ｓ（Ｈ）さんに感謝します。

　上記のＰ（ｎ）の計算で、Ｐ（ｎ）＝（ｎ³−１）ｎ³（ｎ³＋１）/９　と変形してから値が整数になる
ことを示す方が実戦的であろう。正直に告白すると、私は Ｅｘｃｅｌ さんに計算してもらいまし
た．．．！


　上記の証明に関連して次のポリアの定理があることをＳ（Ｈ）さんよりご教示いただいた。

ポリアの定理　　すべての整数 ｘ に対して、多項式 Ｐ（ｘ） が整数値をとるための

　必要十分条件は、整数 Ａ₀，Ａ₁，Ａ₂，・・・，Ａ_ｎ を適当に選び、

　Ｐ(ｘ)＝Ａ₀＋Ａ₁Ｆ₁（ｘ)＋Ａ₂Ｆ₂（ｘ)＋・・・＋Ａ_ｎＦ_ｎ（ｘ)

と書けることである。ただし、

　Ｆ_ｋ(ｘ）＝ｘ(ｘ−１)(ｘ−２)(ｘ−３)・・・(ｘ−ｋ＋１)／ｋ！　とする。


（コメント）　上記の証明は、正にポリアの定理を意識した証明になっていますね！

　上記で述べられたことから、整数値多項式 Ｆｎ(Ｘ） の有用性が実感できたが、平成２１年
４月１７日付けで、Ｓ（Ｈ）さんから、基底の変換

　　　｛ １，ｘ，ｘ²，ｘ³，・・・ｘ^ｎ，・・・ ｝　⇔　｛ １，Ｆ1(ｘ），Ｆ2(ｘ），・・・，Ｆｎ(ｘ），・・・ ｝

の対応表を作ってみては．．．という提案があった。

　対応表があれば、上記のような手順を踏まずに直接的に多項式の別表現が得られる。

　その作り方は単純で、

　　ｘ^ｎ を ｘ で割り、その商を ｘ−１ で割り、その商を ｘ−２ で割り、・・・・

と順次割っていけばよい。そのときの余りを用いて、新しい基底の係数が決定される。

　例えば、　ｘ＝ｘ・１　なので、　ｘ＝１・Ｆ1(ｘ）　である。

　ｘ²＝ｘ・ｘ＝ｘ｛（ｘ−１）・１＋１｝＝ｘ・１＋ｘ（ｘ−１）・１＝１・Ｆ1(ｘ）＋２！・Ｆ2(ｘ）

　ｘ³＝ｘ・ｘ²＝ｘ｛（ｘ−１）・（ｘ＋１）＋１｝＝ｘ［（ｘ−１）｛（ｘ−２）・１＋３｝＋１］
　＝ｘ・１＋ｘ（ｘ−１）・３＋ｘ（ｘ−１）（ｘ−２）・１＝１・Ｆ1(ｘ）＋３！・Ｆ2(ｘ）＋３！・Ｆ3(ｘ）

　・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・

　原理は単純でも計算がだんだん辛くなりそうな．．．予感！

　係数を決定するだけだったら、次のように計算してもできるかな？

　ｘ³＝ａ・Ｆ1(ｘ）＋ｂ・Ｆ2(ｘ）＋ｃ・Ｆ3(ｘ）　において、

　Ｆ1(１）＝１　、Ｆ2(１）＝０　、Ｆ3(１）＝０

　Ｆ1(２）＝２　、Ｆ2(２）＝１　、Ｆ3(２）＝０

　Ｆ1(３）＝３　、Ｆ2(３）＝３　、Ｆ3(３）＝１

なので、　ａ＝１　、　２ａ＋ｂ＝８　、　３ａ＋３ｂ＋ｃ＝２７　より、　ａ＝１　、ｂ＝６　、ｃ＝６

　この方法だと、行列の計算に持ち込めそうですね！

　もう少し計算してみると、

　Ｆ1(１）＝１　、Ｆ2(１）＝０　、Ｆ3(１）＝０　、Ｆ4(１）＝０　、Ｆ5(１）＝０

　Ｆ1(２）＝２　、Ｆ2(２）＝１　、Ｆ3(２）＝０　、Ｆ4(２）＝０　、Ｆ5(２）＝０

　Ｆ1(３）＝３　、Ｆ2(３）＝３　、Ｆ3(３）＝１　、Ｆ4(３）＝０　、Ｆ5(３）＝０

　Ｆ1(４）＝４　、Ｆ2(４）＝６　、Ｆ3(４）＝４　、Ｆ4(４）＝１　、Ｆ5(４）＝０

　Ｆ1(５）＝５　、Ｆ2(５）＝１０　、Ｆ3(５）＝１０　、Ｆ4(５）＝５　、Ｆ5(５）＝１

となって、パスカルの三角形と同様な構造になっていることに気づく。

　この規則性に従って、表を作ってみた。

　この表をもとに、ｘ⁴ 、ｘ⁵ 、ｘ⁶ 、ｘ⁷ 、ｘ⁸ 、ｘ⁹ 、・・・　を計算してみよう。

　ｘ⁴＝ａ・Ｆ1(ｘ）＋ｂ・Ｆ2(ｘ）＋ｃ・Ｆ3(ｘ）＋ｄ・Ｆ4(ｘ）　とおくと、上記の表より、

　１＝ａ
　１６＝２ａ＋ｂ　　より、　ｂ＝１４
　８１＝３ａ＋３ｂ＋ｃ　　より、　ｃ＝８１−３−４２＝３６
　２５６＝４ａ＋６ｂ＋４ｃ＋ｄ　　より、　ｄ＝２５６−４−８４−１４４＝２４

なので、　ｘ⁴＝１・Ｆ1(ｘ）＋１４・Ｆ2(ｘ）＋３６・Ｆ3(ｘ）＋２４・Ｆ4(ｘ）

　ｘ⁵＝ａ・Ｆ1(ｘ）＋ｂ・Ｆ2(ｘ）＋ｃ・Ｆ3(ｘ）＋ｄ・Ｆ4(ｘ）＋ｅ・Ｆ5(ｘ）　とおくと、上記の表より、

　１＝ａ
　３２＝２ａ＋ｂ　　より、　ｂ＝３０
　２４３＝３ａ＋３ｂ＋ｃ　　より、　ｃ＝２４３−３−９０＝１５０
　１０２４＝４ａ＋６ｂ＋４ｃ＋ｄ　　より、　ｄ＝１０２４−４−１８０−６００＝２４０
　３１２５＝５ａ＋１０ｂ＋１０ｃ＋５ｄ＋ｅ　　より、
　　　　　　　　　　　　　　　　　　　　　　　　　　ｅ＝３１２５−５−３００−１５００−１２００＝１２０

なので、　ｘ⁵＝１・Ｆ1(ｘ）＋３０・Ｆ2(ｘ）＋１５０・Ｆ3(ｘ）＋２４０・Ｆ4(ｘ）＋１２０・Ｆ5(ｘ）

　ｘ⁶＝ａ・Ｆ1(ｘ）＋ｂ・Ｆ2(ｘ）＋ｃ・Ｆ3(ｘ）＋ｄ・Ｆ4(ｘ）＋ｅ・Ｆ5(ｘ）＋ｆ・Ｆ6(ｘ）　とおくと、

上記の表より、

　１＝ａ
　６４＝２ａ＋ｂ　　より、　ｂ＝６２
　７２９＝３ａ＋３ｂ＋ｃ　　より、　ｃ＝７２９−３−１８６＝５４０
　４０９６＝４ａ＋６ｂ＋４ｃ＋ｄ　　より、　ｄ＝４０９６−４−３７２−２１６０＝１５６０
　１５６２５＝５ａ＋１０ｂ＋１０ｃ＋５ｄ＋ｅ　　より、
　ｅ＝１５６２５−５−６２０−５４００−７８００＝１８００
　４６６５６＝６ａ＋１５ｂ＋２０ｃ＋１５ｄ＋６ｅ＋ｆ　　より、
　ｆ＝４６６５６−６−９３０−１０８００−２３４００−１０８００＝７２０

なので、

　ｘ⁶＝１・Ｆ1(ｘ）＋６２・Ｆ2(ｘ）＋５４０・Ｆ3(ｘ）＋１５６０・Ｆ4(ｘ）＋１８００・Ｆ5(ｘ）＋７２０・Ｆ6(ｘ）

　ｘ⁷＝ａ・Ｆ1(ｘ）＋ｂ・Ｆ2(ｘ）＋ｃ・Ｆ3(ｘ）＋ｄ・Ｆ4(ｘ）＋ｅ・Ｆ5(ｘ）＋ｆ・Ｆ6(ｘ）＋ｇ・Ｆ7(ｘ）　とおくと、

上記の表より、

　１＝ａ
　１２８＝２ａ＋ｂ　　より、　ｂ＝１２６
　２１８７＝３ａ＋３ｂ＋ｃ　　より、　ｃ＝２１８７−３−３７８＝１８０６
　１６３８４＝４ａ＋６ｂ＋４ｃ＋ｄ　　より、　ｄ＝１６３８４−４−７５６−７２２４＝８４００
　７８１２５＝５ａ＋１０ｂ＋１０ｃ＋５ｄ＋ｅ　　より、
　ｅ＝７８１２５−５−１２６０−１８０６０−４２０００＝１６８００
　２７９９３６＝６ａ＋１５ｂ＋２０ｃ＋１５ｄ＋６ｅ＋ｆ　　より、
　ｆ＝２７９９３６−６−１８９０−３６１２０−１２６０００−１００８００＝１５１２０
　８２３５４３＝７ａ＋２１ｂ＋３５ｃ＋３５ｄ＋２１ｅ＋７ｆ＋ｇ　　より、
　ｇ＝８２３５４３−７−２６４６−６３２１０−２９４０００−３５２８００−１０５８４０＝５０４０

なので、

　ｘ⁷＝１・Ｆ1(ｘ）＋１２６・Ｆ2(ｘ）＋１８０６・Ｆ3(ｘ）＋８４００・Ｆ4(ｘ）＋１６８００・Ｆ5(ｘ）
　　＋１５１２０・Ｆ6(ｘ）＋５０４０・Ｆ7(ｘ）

　ちょっと手計算では辛くなってきたので、以下は、Ｅｘｃｅｌ さんに手伝ってもらおう。

　この表より、

　ｘ⁸＝１・Ｆ1(ｘ）＋２５４・Ｆ2(ｘ）＋５７９６・Ｆ3(ｘ）＋４０８２４・Ｆ4(ｘ）＋１２６０００・Ｆ5(ｘ）
　　＋１９１５２０・Ｆ6(ｘ）＋１４１１２０・Ｆ7(ｘ）＋４０３２０・Ｆ8(ｘ）

　ｘ⁹＝１・Ｆ1(ｘ）＋５１０・Ｆ2(ｘ）＋１８１５０・Ｆ3(ｘ）＋１８６４８０・Ｆ4(ｘ）＋８３４１２０・Ｆ5(ｘ）
　　＋１９０５１２０・Ｆ6(ｘ）＋２３２８４８０・Ｆ7(ｘ）＋１４５１５２０・Ｆ8(ｘ）＋３６２８８０・Ｆ9(ｘ）

　この計算結果は、Ｓ（Ｈ）さんのものと一致する。（ほっと、安心．．．！）

　ところで、　Ｐ（ｘ）＝ａ＋ｂ・Ｆ1(Ｘ）＋ｃ・Ｆ2(Ｘ）＋・・・＋ｄ・Ｆｎ(Ｘ）　の各係数は、連立方程式
を解くことにより得られたが、次のような方法があることをＳ（Ｈ）さんよりご教示いただいた。

　差分の考え方を用いる。下記の表は、ニュートン以来の差分の並べ方とのことである。

何となく、（ａ−ｂ）^ｎ　の展開公式に似ている！　ここで、

Δａ_ｎ＝ａ_ｎ+1−ａ_ｎ　、　Δ²ａ_ｎ＝Δａ_ｎ+1−Δａ_ｎ　、　・・・　、　Δ^kａ_ｎ＝Δ^k-1ａ_ｎ+1−Δ^k-1ａ_ｎ

とおくと、上記の表は、次のように整理される。

　このとき、次の事実が知られている。

　関数 Ｆ（ｘ）＝ｘ^ｎ について、　ａ_ｎ＝Ｆ（ｎ）　で数列 ｛ ａ_ｎ ｝ を定める。

　ｘ^ｎ ＝ ａ₀＋Δａ₀ｘ＋Δ²ａ₀ｘ（ｘ−１）/２！＋Δ³ａ₀ｘ（ｘ−１）（ｘ−２）/３！＋・・・

が成り立つ。

　ｎ＝３　の場合に確認してみよう。

　　ｘ³＝ａ＋ｂｘ＋ｃｘ（ｘ−１）＋ｄｘ（ｘ−１）（ｘ−２）　とおく。

　ｘ＝０　のとき、　ａ₀＝ａ

　ｘ＝１　のとき、　ａ₁＝ａ＋ｂ

　ｘ＝２　のとき、　ａ₂＝ａ＋２ｂ＋２ｃ

　ｘ＝３　のとき、　ａ₃＝ａ＋３ｂ＋６ｃ＋６ｄ

　　以上の計算から、　ｂ＝Δａ₀　、　ｂ＋２ｃ＝Δａ₁　なので、　２ｃ＝Δ²ａ₀

　同様にして、　ｂ＋４ｃ＋６ｄ＝Δａ₂　なので、　２ｃ＋６ｄ＝Δ²ａ₁　　よって、　６ｄ＝Δ³ａ₀

　したがって、

　　　ｘ³＝ａ₀＋Δａ₀ｘ＋Δ²ａ₀ｘ（ｘ−１）/２！＋Δ³ａ₀ｘ（ｘ−１）（ｘ−２）/３！

と書けることが示された。

　この展開式を用いると、

　　ｘ³＝１・Ｆ1(ｘ）＋３！・Ｆ2(ｘ）＋３！・Ｆ3(ｘ）＝１・Ｆ1(ｘ）＋６・Ｆ2(ｘ）＋６・Ｆ3(ｘ）

　すなわち、　ｘ³＝０＋１・Ｆ1(ｘ）＋６・Ｆ2(ｘ）＋６・Ｆ3(ｘ）　における係数は、次の差分の計算
から直ちに得られる。

　読者の方も

　　ｘ⁴＝１・Ｆ1(ｘ）＋１４・Ｆ2(ｘ）＋３６・Ｆ3(ｘ）＋２４・Ｆ4(ｘ）

　　ｘ⁵＝１・Ｆ1(ｘ）＋３０・Ｆ2(ｘ）＋１５０・Ｆ3(ｘ）＋２４０・Ｆ4(ｘ）＋１２０・Ｆ5(ｘ）

について、差分を利用して確認してみて下さい。

　実際に、

（コメント）　やっている計算はほとんど連立方程式の計算と同等ですが、何となくスッキリで
　　　　　　すね！


　Ｓ（Ｈ）さんの計算によれば、

　ｎ⁹−ｎ³＝５０４Ｆ₂（ｘ)＋１８１４４Ｆ₃（ｘ)＋１８６４８０Ｆ₄（ｘ)＋８３４１２０Ｆ₅（ｘ)

　＋１９０５１２０Ｆ₆（ｘ)＋２３２８４８０Ｆ₇（ｘ)＋１４５１５２０Ｆ₈（ｘ)＋３６２８８０Ｆ₉（ｘ)

と書けるので、各係数が９の倍数であることから、ｎ⁹−ｎ³ は、９の倍数となる。


　ｘ^ｎ を、｛　１，Ｆ1(ｘ），Ｆ2(ｘ），・・・，Ｆｎ(ｘ） ｝ で表す問題は、当ＨＰの「ベル数」でも取り上げ
られた。（平成２１年４月１９日付けで、Ｓ（Ｈ）さんより、ご指摘いただきました！謝謝！）

　ｘ の関数 Ｐ_k（ｘ） （ ｋ は、自然数）を、　Ｐ_k（ｘ）＝ｘ(ｘ−１)・・・(ｘ−ｋ＋１)　と定義する。

このとき、　Ｐ_k（ｎ）＝_ｎＰ_ｋ　である。 特に、　Ｐ_ｎ（ｎ）＝ｎ！　である。

　ここで、　_ｎＰ₀＝１　であるので、 Ｐ₀（ｘ）＝１と約束することは理にかなったものだろう。

　上記で考えた整数値多項式　Ｆ_ｋ（ｘ)　との関係は、明らかに、　Ｐ_k（ｘ）＝ｋ！・Ｆ_ｋ（ｘ)

　この Ｐ_k（ｘ）　（ｋ＝１、２、３、・・・）　を用いて、多項式 （ｘ＋１）^ｎ　が表される。

例えば、

　（ｘ＋１）³＝ｘ(ｘ−１)(ｘ−２)＋６ｘ(ｘ−１)＋７ｘ＋１＝Ｐ₃（ｘ）＋６Ｐ₂（ｘ）＋７Ｐ₁（ｘ）＋Ｐ₀（ｘ）

　このとき、ｘ に、ｘ−１ を代入すると、

　ｘ³＝(ｘ−１)(ｘ−２)（ｘ−３）＋６(ｘ−１)（ｘ−２）＋７（ｘ−１）＋１

なので、両辺に ｘ を掛けると、

　ｘ⁴＝ｘ(ｘ−１)(ｘ−２)（ｘ−３）＋６ｘ(ｘ−１)（ｘ−２）＋７ｘ（ｘ−１）＋ｘ

　＝Ｐ₄（ｘ）＋６Ｐ₃（ｘ）＋７Ｐ₂（ｘ）＋Ｐ₁（ｘ）＝２４・Ｆ₄（ｘ)＋３６・Ｆ₃（ｘ)＋１４・Ｆ₂（ｘ)＋Ｆ₁（ｘ)

　＝１・Ｆ₁（ｘ)＋１４・Ｆ₂（ｘ)＋３６・Ｆ₃（ｘ)＋２４・Ｆ₄（ｘ)

　この結果は、上記で得られたものと一致する。

　このように、基底の変換の係数は、第２種スターリング数からも得られる点が興味深い。


（コメント）　この第２種スターリング数との関係から、整数値多項式の定理の名前に、「ポ
　　　　　　リア」がつくものがあることを、思わず合点してしまいました。


　平成２１年４月２２日付けで、Ｓ（Ｈ）さんが、幾つかの問題を提起された。

１．Ｄｅｔｅｒｍｉｎｅ　ｔｈｅ　ｇｒｅａｔｅｓｔ　ｃｏｍｍｏｎ　ｄｉｖｉｓｏｒ　ｏｆ　ｔｈｅ　ｅｌｅｍｅｎｔｓ　ｏｆ
　ｔｈｅ　ｓｅｔ　｛ ｎ¹³−ｎ ｜ ｎ∈Ｚ ｝．
　（［ＰＪ　pp．１１０］　ＵＣ　Ｂｅｒｋｅｌｅｙ　Ｐｒｅｌｉｍｉｎａｒｙ　Ｅｘａｍ　１９９０）

２．Ｗｈａｔ　ｉｓ　ｔｈｅ　ｇｒｅａｔｅｓｔ　ｃｏｍｍｏｎ　ｄｉｖｉｓｏｒ　ｏｆ　ｔｈｅ　ｓｅｔ　ｏｆ　ｎｕｍｂｅｒｓ
　｛ １６^ｎ＋１０ｎ−１ ｜ ｎ＝１、２、・・・ ｝？

３．Ｓｕｐｐｏｓｅ　ｔｈａｔ　ｐ　ｉｓ　ａ　ｐｒｉｍｅ　ｎｕｍｂｅｒ　ａｎｄ　ｉｓ　ｇｒｅａｔｅｒ　ｔｈａｎ　３．
　Ｐｒｏｖｅ　ｔｈａｔ　７^ｐ−６^ｐ−１　ｉｓ　ｄｉｖｉｓｉｂｌｅ　ｂｙ　４３．（Ｉｒａｎ　１９９４）


　その中の「Ｂｅｒｋｅｌｅｙ」という文字に惹かれ、まず、１．の問題を考えてみようと思う。

　東京工業大学の問題のように、いくつか実験をしてみよう。

　ｎ＝１　のとき、　ｎ¹³−ｎ＝０

　ｎ＝２　のとき、　ｎ¹³−ｎ＝８１９２−２＝８１９０＝２・３²・５・７・１３

　ｎ＝３　のとき、　ｎ¹³−ｎ＝１５９４３２３−３＝１５９４３２０＝２⁴・３・５・７・１３・７３

と計算してみると、　２・３・５・７・１３＝２７３０　の倍数となっているような．．．予感！

　実は、ｎ¹³−ｎ　は、２７３０ で割り切れることが次のように示される。２７３０ が求める最
大公約数（ｇｒｅａｔｅｓｔ　ｃｏｍｍｏｎ　ｄｉｖｉｓｏｒ）であることは明らかだろう。

　フェルマーの定理を用いるのがエレガントかな？

（証明）　フェルマーの定理により、

　ｎ²≡ｎ　（ｍｏｄ　２）　、ｎ³≡ｎ　（ｍｏｄ　３）　、ｎ⁵≡ｎ　（ｍｏｄ　５）　、ｎ⁷≡ｎ　（ｍｏｄ　７）

　ｎ¹³≡ｎ　（ｍｏｄ　１３）　が成り立つ。　ところで、

ｎ¹³−ｎ＝ｎ（ｎ¹²−１）＝（ｎ²−ｎ）（ｎ¹¹＋ｎ¹⁰＋・・・＋ｎ＋１）≡０　（ｍｏｄ　２）

ｎ¹³−ｎ＝ｎ（ｎ¹²−１）＝（ｎ³−ｎ）（ｎ¹⁰＋ｎ⁸＋・・・＋ｎ²＋１）≡０　（ｍｏｄ　３）

ｎ¹³−ｎ＝ｎ（ｎ¹²−１）＝（ｎ⁵−ｎ）（ｎ⁸＋ｎ⁴＋１）≡０　（ｍｏｄ　５）

ｎ¹³−ｎ＝ｎ（ｎ¹²−１）＝（ｎ⁷−ｎ）（ｎ⁶＋１）≡０　（ｍｏｄ　７）

ｎ¹³−ｎ≡０　（ｍｏｄ　１３）

なので、ｎ¹³−ｎ　は、２、３、５、７、１３　すなわち、２７３０ で割り切れる。　　（証終）


　次に、２．の問題を考えてみよう。　１．と同様に、まず実験してみよう。

　ｎ＝１　のとき、　１６^ｎ＋１０ｎ−１＝１６＋１０−１＝２５＝５²

　ｎ＝２　のとき、　１６^ｎ＋１０ｎ−１＝２５６＋２０−１＝２７５＝５²・１１

と計算してみると、　５²＝２５　の倍数となっているような．．．予感！

　実は、１６^ｎ＋１０ｎ−１　は、２５ で割り切れることが次のように示される。２５ が求める
最大公約数（ｇｒｅａｔｅｓｔ　ｃｏｍｍｏｎ　ｄｉｖｉｓｏｒ）であることは明らかだろう。

　１．とは異なる手法で解いてみよう。

（解）　Ｆ（ｎ）＝１６^ｎ＋１０ｎ−１　とおくと、

　Ｆ（ｎ＋１）−Ｆ（ｎ）＝１６^ｎ+1＋１０（ｎ＋１）−１−（１６^ｎ＋１０ｎ−１）＝１５・１６^ｎ＋１０

　＝１５・（１５^ｎ＋ｎ・１５^ｎ-1＋・・・＋ｎ・１５＋１）＋１０＝１５^ｎ+1＋ｎ・１５^ｎ＋・・・＋ｎ・１５²＋２５

　＝２５（９・１５^ｎ-1＋９ｎ・１５^ｎ-1＋・・・＋９ｎ＋１）

は、２５ で割り切れる。

　このとき、Ｆ（ｎ）＝１６^ｎ＋１０ｎ−１　が２５ で割り切れることが数学的帰納法により示される。

　ｎ＝１　のとき、　Ｆ（１）＝１６＋１０−１＝２５　は、２５ で割り切れる。

　よって、　ｎ＝１　のとき成り立つ。

　ｎ＝ｋ （ｋ≧１）　のとき成り立つと仮定する。すなわち、Ｆ（ｋ）＝１６^ｋ＋１０ｋ−１　は２５ で

　割り切れる。

　ｎ＝ｋ＋１　のとき、　Ｆ（ｋ＋１）−Ｆ（ｋ）は、２５ で割り切れ、かつ、Ｆ（ｋ）　が２５ で割り切

　れるので、Ｆ（ｋ＋１）は、２５ で割り切れる。

　よって、ｎ＝ｋ＋１　のときも成り立つ。

以上から、数学的帰納法により、すべての自然数 ｎ に対して、

　Ｆ（ｎ）＝１６^ｎ＋１０ｎ−１　が２５ で割り切れる。　　（終）


　最後に、３．を考えてみる。例によって、実験してみよう。 ｐ は、３以上の素数なので、

　ｐ＝５　のとき、　７⁵−６⁵−１＝１６８０７−７７７６−１＝９０３０＝２・３・５・７・４３

　ｐ＝７　のとき、　７⁷−６⁷−１＝８２３５４３−２７９９３６−１＝５４３６０６＝２・３・７²・４３²

　ｐ＝１１　のとき、

　７¹¹−６¹¹−１＝１９７７３２６７４３−３６２７９７０５６−１
＝１６１４５２９６８６＝２・３・７・１１・４３・６７・１２１３

　ｐ＝１３　のとき、　７¹³−６¹³−１＝８３８２８３１６３９０＝２・３・５・７・１３・４３²・１６６０７

　ｐ＝１７　のとき、

　７¹⁷−６¹⁷−１＝２１５７０３８５４５４２４７０＝２・３・５・７・１７・４３・２３８９・５８８１７３

　ｐ＝１９　のときは、Ｅｘｃｅｌ さんが、オーバーフローになってしまい計算ができなかった。


　何となく上記の計算から、２・３・７・４３＝１８０６　の倍数となっているような．．．予感！
はするが、前の問題達のように確証できないところが口惜しい。

　もっとも、問題は、「４３で割り切れる」ことを示せばいいので、それほど深入りしなくても
よいのかな？

　因みに、

　ｐ＝３　のとき、　７³−６³−１＝３４３−２１６−１＝１２６

　ｐ＝２　のとき、　７²−６²−１＝４９−３６−１＝１２

から、「４３で割り切れる」ことを示すために、「素数 ｐ＞３」という条件は外せない。

　（解答準備中）


（追記）　令和５年９月１７日付け

　平成２１年４月２２日以来、（解答準備中）であったが、ＨＮ「ＤＹ」さんより、解答をメールで
いただいた。ＤＹさんに感謝します。

３．Ｓｕｐｐｏｓｅ　ｔｈａｔ　ｐ　ｉｓ　ａ　ｐｒｉｍｅ　ｎｕｍｂｅｒ　ａｎｄ　ｉｓ　ｇｒｅａｔｅｒ　ｔｈａｎ　３．
　Ｐｒｏｖｅ　ｔｈａｔ　７^ｐ−６^ｐ−１　ｉｓ　ｄｉｖｉｓｉｂｌｅ　ｂｙ　４３．（Ｉｒａｎ　１９９４）

　邦訳すれば、

　ｐが３より大きい素数のとき、７^ｐ−６^ｐ−１ が４３の倍数であることを示せ

（解）　４３を法として、７⁶＝（７³）²＝３４３²≡（−１）²＝１、６⁶＝（６³）²＝２１６²≡１²＝１

であり、３より大きい素数は、Ｎを自然数として、　（１）　６Ｎ−１　（２）　６Ｎ＋１　の何れかの

形で表せる。

（１）　ｐ＝６Ｎ−１　のとき、４３を法として、７⁶≡１、７³≡−１、６³≡１　なので、

　７^ｐ−６^ｐ−１＝７^6N-1−６^6N-1−１≡７^6N+5−６^6N+2−１≡７⁵−６²−１
　≡−４９−３６−１＝−８６≡０

（２）　ｐ＝６Ｎ＋１　のとき、４３を法として、７⁶≡１、６⁶≡１　なので、

　７^ｐ−６^ｐ−１＝７^6N+1−６^6N+1−１≡７−６−１＝０

　何れにしても、７^ｐ−６^ｐ−１は４３の倍数である。　　（終）

＃証明から分かるように、結局、「ｐは素数」とは限らずとも、６と互いに素な自然数ならば
　成り立つということになります。


（コメント）　鮮やかな証明ですね！感動しました。


　平成２１年４月２４日付けで、Ｓ（Ｈ）さんが、新たに幾つかの問題を提起された。

１．Ｐｒｏｖｅ　ｔｈａｔ　１７^ｎ−１２^ｎ−２４^ｎ＋１９^ｎ　ｉｓ　ｄｉｖｉｓｉｂｌｅ　ｂｙ　３５，　ｆｏｒ　ａｎｙ
　ｎａｔｕｒａｌ　ｎｕｍｂｅｒ　ｎ．

　（Ｇｅｔ　ｔｈｅ　ｄｉｖｉｓｏｒ　ｄ　ｓｕｃｈ　ｔｈａｔ　ｄ｜１７^ｎ−１２^ｎ−２４^ｎ＋１９^ｎ　ｆｏｒ　ａｎｙ　ｎａｔｕｒａｌ　ｎｕｍｂｅｒ　ｎ．）

２．Ｐｒｏｖｅ　ｔｈｅ　ｆｏｌｌｏｗｉｎｇ ：

（１）　３^6ｎ−２^6ｎ ｉｓ　ｄｉｖｉｓｉｂｌｅ　ｂｙ　３５，ｆｏｒ　ｅｖｅｒｙ　ｐｏｓｉｔｉｖｅ　ｉｎｔｅｇｅｒ　ｎ ；

（Ｇｅｔ　ｔｈｅ　ｄｉｖｉｓｏｒ　ｄ　ｓｕｃｈ　ｔｈａｔ　ｄ｜３^6ｎ−２^6ｎ　ｆｏｒ　ｅｖｅｒｙ　ｐｏｓｉｔｉｖｅ　ｎｕｍｂｅｒ　ｎ．）

（２）　ｎ⁵−５ｎ³＋４ｎ ｉｓ　ｄｉｖｉｓｉｂｌｅ　ｂｙ　１２０，ｆｏｒ　ｅｖｅｒｙ　ｉｎｔｅｇｅｒ　ｎ ；

（Ｇｅｔ　ｔｈｅ　ｄｉｖｉｓｏｒ　ｄ　ｓｕｃｈ　ｔｈａｔ　ｄ｜ｎ⁵−５ｎ³＋４ｎ　ｆｏｒ　ｅｖｅｒｙ　ｉｎｔｅｇｅｒ　ｎ．）

（３）　ｆｏｒ　ａｌｌ　ｉｎｔｅｇｅｒｓ　ｍ　ａｎｄ　ｎ ，ｍｎ（ｍ⁶⁰−ｎ⁶⁰） ｉｓ　ｄｉｖｉｓｉｂｌｅ
　ｂｙ　５６７８６７３０．（Ｈｉｎｔ ：　５６７８６７３０＝２・３・５・７・１１・１３・３１・６１．）

（４）　Ｐｒｏｖｅ　ｔｈａｔ　ｎ²＋３ｎ＋５　ｉｓ　ｎｅｖｅｒ　ｄｉｖｉｓｉｂｌｅ　ｂｙ　１２１　ｆｏｒ　ａｎｙ
　ｐｏｓｉｔｉｖｅ　ｉｎｔｅｇｅｒ　ｎ．


（１．の解）　ｎ＝１　のとき、　１７^ｎ−１２^ｎ−２４^ｎ＋１９^ｎ＝０　なので、すべての自然数で割
　り切れる。

ｎ＝２　のとき、　１７^ｎ−１２^ｎ−２４^ｎ＋１９^ｎ＝−７０＝−３５・２

ｎ＝３　のとき、　１７^ｎ−１２^ｎ−２４^ｎ＋１９^ｎ＝−３７８０＝−３５・２²・３³

ｎ＝４　のとき、　１７^ｎ−１２^ｎ−２４^ｎ＋１９^ｎ＝−１３８６７０＝−３５・２・７・２８３

　・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・

　素因数の状況を表にしてみると、

　このことから、すべての自然数 ｎ に対して、１７^ｎ−１２^ｎ−２４^ｎ＋１９^ｎ　は、

　２　、　５　、　７　、１０　、１４　、３５　、７０

で割り切れることが予想される。

（イ）　１７^ｎ−１２^ｎ−２４^ｎ＋１９^ｎ　が、２ で割り切れることの証明

　１７^ｎ−１２^ｎ−２４^ｎ＋１９^ｎ≡１−０−０＋１＝２≡０　（ｍｏｄ　２）　より、明らか。

（ロ）　１７^ｎ−１２^ｎ−２４^ｎ＋１９^ｎ　が、５ で割り切れることの証明

　１７^ｎ−１２^ｎ−２４^ｎ＋１９^ｎ≡２^ｎ−２^ｎ−（−１）^ｎ＋（−１）^ｎ＝０　（ｍｏｄ　５）　より、明らか。

（ハ）　１７^ｎ−１２^ｎ−２４^ｎ＋１９^ｎ　が、７ で割り切れることの証明

　１７^ｎ−１２^ｎ−２４^ｎ＋１９^ｎ≡３^ｎ−（−２）^ｎ−３^ｎ＋（−２）^ｎ＝０　（ｍｏｄ　７）　より、明らか。

（ニ）　１７^ｎ−１２^ｎ−２４^ｎ＋１９^ｎ　が、１０ で割り切れることの証明

　（イ）、（ロ）　より、明らか。

（ホ）　１７^ｎ−１２^ｎ−２４^ｎ＋１９^ｎ　が、１４ で割り切れることの証明

　（イ）、（ハ）　より、明らか。

（ヘ）　１７^ｎ−１２^ｎ−２４^ｎ＋１９^ｎ　が、３５ で割り切れることの証明

　（ロ）、（ハ）　より、明らか。

（ト）　１７^ｎ−１２^ｎ−２４^ｎ＋１９^ｎ　が、７０ で割り切れることの証明

　（ハ）、（ニ）　より、明らか。

以上から、　すべての自然数 ｎ に対して、１７^ｎ−１２^ｎ−２４^ｎ＋１９^ｎ　は、

　２　、　５　、　７　、１０　、１４　、３５　、７０

で割り切れる。

（２．（１）の解）　３^6ｎ−２^6ｎ＝７２９^ｎ−６４^ｎ≡（−１）^ｎ−（−１）^ｎ＝０　（ｍｏｄ　５）

　３^6ｎ−２^6ｎ＝７２９^ｎ−６４^ｎ≡１^ｎ−１^ｎ＝０　（ｍｏｄ　７）

以上から、　すべての自然数 ｎ に対して、３^6ｎ−２^6ｎ　は、３５　で割り切れる。

　ところで、　ｎ＝１　のとき、　３^6ｎ−２^6ｎ＝７２９−６４＝６６５＝５・７・１９

ｎ＝２　のとき、　３^6ｎ−２^6ｎ＝７２９²−６４²＝５２７３４５＝５・７・１３・１９・６１

ｎ＝３　のとき、　３^6ｎ−２^6ｎ＝７２９³−６４³＝３８７１５８３４５＝５・７・１９・５７７・１００９

ｎ＝４　のとき、

　３^6ｎ−２^6ｎ＝７２９⁴−６４⁴＝２８２４１２７５９２６５＝５・７・１３・１９・６１・９７・５５２１

　　・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・

　上記の計算から、すべての自然数 ｎ に対して、３^6ｎ−２^6ｎ　は、

　　　　　５　、　７　、１９　、３５　、９５　、１３３　、６６５

の各数で割り切れることが予想される。（５、７ については、証明済み）

　３^6ｎ−２^6ｎ　が １９ で割り切れることは、

　３^6ｎ−２^6ｎ＝７２９^ｎ−６４^ｎ≡７^ｎ−７^ｎ＝０　（ｍｏｄ　１９）　より明らかだろう。

以上から、　すべての自然数 ｎ に対して、３^6ｎ−２^6ｎ　は、

　５　、　７　、１９　、３５　、９５　、１３３　、６６５

の各数で割り切れる。


（２．（２）の解）　　ｎ⁵−５ｎ³＋４ｎ＝（ｎ−２）（ｎ−１）ｎ（ｎ＋１）（ｎ＋２）　は連続する５整数
　の積である。

　ｎ≧２のとき、　ｎ⁵−５ｎ³＋４ｎ＝５！・_ｎ+2Ｃ₅　で、_ｎ+2Ｃ₅　は整数なので、

　ｎ⁵−５ｎ³＋４ｎ　は、５！＝１２０　で割り切れる。

　ｎ＝０、１　のときは、　ｎ⁵−５ｎ³＋４ｎ＝０　で、もちろん、１２０　で割り切れる。

　負の整数 ｎ については、 ｎ＝−ｍ　（ｍは自然数）　として、同様に示される。

以上から、　すべての整数 ｎ に対して、ｎ⁵−５ｎ³＋４ｎ　は、１２０　で割り切れる。

　ｎ＝３　のとき、_ｎ+2Ｃ₅＝１　なので、すべての整数 ｎ に対して、ｎ⁵−５ｎ³＋４ｎ　を割り

切る数は、１２０の約数全てである。


（追記）　平成２１年５月２日付けで、Ｓ（Ｈ）さんが、新たな問題を提起された。

　１¹⁹⁸³＋２¹⁹⁸³＋３¹⁹⁸³＋・・・＋１９８６¹⁹⁸³≡０　（ｍｏｄ　１９８７）を示せ。

　一見すると難しそうな雰囲気だが、次のように考えれば易しいだろう。

　１９８７ は素数で、１９８３と１９８７は互いに素である。

　このとき、

　１９８６¹⁹⁸³≡（−１）¹⁹⁸³≡−１¹⁹⁸³　（ｍｏｄ　１９８７）

　１９８５¹⁹⁸³≡（−２）¹⁹⁸³≡−２¹⁹⁸³　（ｍｏｄ　１９８７）

　１９８４¹⁹⁸³≡（−３）¹⁹⁸³≡−３¹⁹⁸³　（ｍｏｄ　１９８７）

　　・・・・・・・・・・・・・・・・・・・・

　９９４¹⁹⁸³≡（−９９３）¹⁹⁸³≡−９９３¹⁹⁸³　（ｍｏｄ　１９８７）

よって、

　１¹⁹⁸³＋２¹⁹⁸³＋３¹⁹⁸³＋・・・＋９９３¹⁹⁸³＋９９４¹⁹⁸³＋・・・＋１９８６¹⁹⁸³

≡１¹⁹⁸³＋２¹⁹⁸³＋・・・＋９９３¹⁹⁸³−９９３¹⁹⁸³−・・・−２¹⁹⁸³−１¹⁹⁸³＝０　（ｍｏｄ　１９８７）

したがって、１¹⁹⁸³＋２¹⁹⁸³＋３¹⁹⁸³＋・・・＋９９３¹⁹⁸³＋９９４¹⁹⁸³＋・・・＋１９８６¹⁹⁸³　は、

１９８７で割り切れる。


（コメント）　類題がたくさん作れそう．．．。


　DD++さんからのコメントです。（平成２８年１月５日付け）

　任意の正の整数nに対し、a[n] = 19ⁿ+2*(-16)^n-1 が 7の倍数であることを示せ。

　これは、東京工業大（１９８６年）の問題

　整数 ａ_ｎ＝１９^ｎ＋（−１）^ｎ-1２^4ｎ-3 （ｎ＝１、２、３、・・・）のすべてを割り切る素数を
求めよ。

と同じ趣旨のもの。略証ですが、とりあえず受験での常套手段２種４つ。

[解法1]・・・（合同式利用）

　a[n] = 19ⁿ+2*(-16)^n-1 ≡ 5ⁿ + 2*5^n-1 ≡ 7*5^n-1 ≡ 0　(mod 7)

[解法2-1]・・・（数学的帰納法利用　その1）

　19^k+1+2*(-16)^k =  19{19^k+2*(-16)^k-1} - 7*10*(-16)^k-1　と  19¹+2*(-16)⁰ = 7*3 から帰
納的に成立。

[解法2-2]・・・（数学的帰納法利用　その2）

　19^k+1+2*(-16)^k = 7*5*19^k - 16{19^k+2*(-16)^k-1}　と 19¹+2*(-16)⁰ = 7*3 から帰納的に
成立。

[解法2-3]・・・（数学的帰納法利用　その3）

　ｘ² = 3ｘ+304　の解が、ｘ = 19、-16 であるので、

19^k+2+2*(-16)^k+1 = 3{19^k+1+2*(-16)^k} + 304{19^k+2*(-16)^k-1}　と 19¹+2*(-16)⁰ = 7*3 と
19²+2*(-16)¹ = 7*47 から帰納的に成立。


　Ｓ（Ｈ）さんから新しい問題が出題されました。（平成２８年１月７日付け）

　２³ⁿ−７ｎ−１は、４９の倍数であることを証明せよ。


　DD++さんからのコメントです。（平成２８年１月７日付け）

　２³ⁿ−７ｎ−１＝(Σ_k=1〜n 7・８^k-1 ) −７ｎ ≡ ( Σ_k=1〜n 7 ) −７ｎ ＝０　 (mod ４９)


（コメント）　２³ⁿ−１＝Σ_k=1〜n 7・８^k-1　という発想が素晴らしいですね！なかなか思いつき
　　　　　　ません。あとは、7・８^k-1＝７・（７＋１）^k-1≡７　 (mod ７²)　という合同式特有の式
　　　　　　変形から明らかですね。


　Ｓ（Ｈ）さんからさらなる試練をいただきました。（平成２８年１月１０日付け）

（１）　Prove that　8^n - 3^n is divisiible by 5 for all natural numbers n
（２）　Prove that　11^n + 8^n - 3^n is divisiible by 4 for all natural numbers n
（３）　Prove that　2*13^n + 11^n + 8^n - 3^n is divisiible by 2 for all natural numbers n

　Ｓ（Ｈ）さんからは、線型漸化式を作る発想で証明せよとのことであるが、数学的帰納法が
手っ取り早い気がする。

（１）の証明：　ｎ＝１のとき、8^1 - 3^1=5　より、５の倍数となり、ｎ＝１のとき成り立つ。

　ｎ＝ｋ（ｋ≧１）のとき成り立つと仮定する。すなわち、 8^ｋ - 3^ｋ　は５の倍数。

　　このとき、　8^ｋ - 3^ｋ=５ｎ　（ｎは整数）　とおけるので、　8^ｋ = 3^ｋ+５ｎ

　　よって、　8^(ｋ+1) - 3^(ｋ+1)=8(3^ｋ+5ｎ)- 3^(ｋ+1)=5・3^ｋ+5(8ｎ)　は５の倍数となり、

　命題は、ｎ＝ｋ＋１の時も成り立つ。

　したがって、すべての自然数ｎに対して、8^n - 3^n　は５の倍数　（証終）

　（２）（３）も同様に、数学的帰納法で示される。


　DD++さんからのコメントです。（平成２８年１月１１日付け）　

　（３）については、数学的帰納法を用いなくても次のように示されます。

　ｎの偶奇にかかわらず、４つの項のうち、偶数が２つで奇数も２つあるので、合計は偶数。


　Ｓ（Ｈ）さんから新しい問題が出題されました。（平成３０年９月２５日付け）

（１）　a (n) = 4^(2*n - 1) + 3^(n + 1)　(n∈N)  は、13の倍数である（信州大）ことを、a(n)が
　　満たす漸化式をつくることにより証明せよ。

（２）　a (n) = 10^n - (-1)^n　(n∈N)　は、11の倍数である（2001 津田塾大學）ことを、a(n)
　　 が満たす漸化式をつくることにより証明せよ。

（３）　任意の整数 n に対し、ｎ⁹−ｎ³ は９で割り切れることを示せ。（京都大学文系（2001年））


（コメント）　平成３０年９月２９日付け

　（３）は通常次のように解かれるだろう。

（解）　ｎ⁹−ｎ³＝ｎ³（ｎ⁶−１）＝ｎ³（ｎ³−１）（ｎ³＋１）

ｎ＝３ｋ（ｋは整数）のとき、ｎ³＝２７ｋ³　より、明らかに、ｎ⁹−ｎ³ は９で割り切れる。

ｎ＝３ｋ＋１（ｋは整数）のとき、ｎ³−１＝２７ｋ³＋２７ｋ²＋９ｋ＝９（３ｋ³＋３ｋ²＋ｋ）　より、

　　　ｎ⁹−ｎ³ は９で割り切れる。

ｎ＝３ｋ−１（ｋは整数）のとき、ｎ³＋１＝２７ｋ³−２７ｋ²＋９ｋ＝９（３ｋ³−３ｋ²＋ｋ）　より、

　　　ｎ⁹−ｎ³ は９で割り切れる。

　以上から、任意の整数 n に対し、ｎ⁹−ｎ³ は９で割り切れる。　　（終）

　この別解として、Ｓ（Ｈ）さんは、漸化式を利用した解法を推奨されている。どのような解法
なのか、大いに興味がある。

　大学教授のＨａｒｖｅｙ　Ｐ．Ｄａｌｅ さんの結果（Feb 11 2015）によれば、ａ（ｎ）＝ｎ⁹−ｎ³　は
次の漸化式を満たすという。

ａ（ｎ）＝１０ａ(n-1)−４５ａ(n-2)＋１２０ａ(n-3)−２１０ａ(n-4)＋２５２ａ(n-5)
　　　　　　　　　　　　　　　　　−２１０ａ(n-6)＋１２０ａ(n-7)−４５ａ(n-8)＋１０ａ(n-9)−ａ(n-10)

　この長い漸化式を見て、途方に暮れてしまう．．．。

　平成３０年９月２９日付けでＳ（Ｈ）さんからご提示あった解答

　a[1]＝0、a[2]＝9*56、a[3]＝9*2184、a[4]＝9*29120、a[5]＝9*217000、a[6]＝9*1119720、
　a[7]＝9*4483696、a[8]＝9*14913024、a[9]＝9*43046640、a[10]＝9*111111000

から、初期値が全て９で割り切れるので、漸化式より、任意の整数 n に対し、ｎ⁹−ｎ³ は９
で割り切れる。

を見て、結局は、数学的帰納法だよね．．．。

　手計算で漸化式を作るのも大変だし、初期値を計算するのも大変だし、漸化式を用いる解
法は現実的ではないような．．．そんな雰囲気。


　そんな訳で、Ｓ（Ｈ）さんの追体験をしてみようということになり、漸化式を作ることに挑戦し
てみた。（平成３０年１０月１日付け）

　普段は、数理現象から漸化式を立てて、それを解いて一般項を求めるわけであるが、ここ
で、逆な計算を行ってみよう。すなわち、数列の一般項から、その数列が満たすべき漸化式
を求めたい。

例　ａ_ｎ＝２ｎ＋１　のとき、ａ_ｎ+1＝２（ｎ＋１）＋１＝（２ｎ＋１）＋１＝ａ_ｎ＋２

　　よって、求める漸化式は、　ａ₁＝３　、ａ_ｎ+1＝ａ_ｎ＋２

例　ａ_ｎ＝ｎ²　のとき、ａ_ｎ+1＝（ｎ＋１）²＝ｎ²＋２ｎ＋１＝ａ_ｎ＋２ｎ＋１

　ｂ_ｎ＝ａ_ｎ+1−ａ_ｎ＝２ｎ＋１　が満たすべき漸化式は、　ｂ₁＝３　、ｂ_ｎ+1＝ｂ_ｎ＋２

よって、求める漸化式は、　ａ₁＝１　、ａ₂＝４　、ａ_ｎ+2−ａ_ｎ+1＝ａ_ｎ+1−ａ_ｎ＋２　より、

　ａ₁＝１　、ａ₂＝４　、ａ_ｎ+2−２ａ_ｎ+1＋ａ_ｎ＝２

例　ａ_ｎ＝ｎ³　のとき、ａ_ｎ+1＝（ｎ＋１）³＝ｎ³＋３ｎ²＋３ｎ＋１＝ａ_ｎ＋３ｎ²＋３ｎ＋１

　ｂ_ｎ＝ａ_ｎ+1−ａ_ｎ＝３ｎ²＋３ｎ＋１　とおくと、　ｂ_ｎ+1＝３（ｎ＋１）²＋３（ｎ＋１）＋１

　よって、　ｃ_ｎ＝ｂ_ｎ+1−ｂ_ｎ＝６ｎ＋６　とおくと、　ｃ_ｎ+1＝６ｎ＋１２＝ｃ_ｎ＋６

　これより、　ｂ_ｎ+2−ｂ_ｎ+1＝ｂ_ｎ+1−ｂ_ｎ＋６　すなわち、　ｂ_ｎ+2−２ｂ_ｎ+1＋ｂ_ｎ＝６

よって、　ａ_ｎ+3−ａ_ｎ+2−２（ａ_ｎ+2−ａ_ｎ+1）＋ａ_ｎ+1−ａ_ｎ＝６　より、求める漸化式は、

　ａ₁＝１　、ａ₂＝８　、ａ₃＝２７　、ａ_ｎ+3−３ａ_ｎ+2＋３ａ_ｎ+1−ａ_ｎ＝６

例　ａ_ｎ＝３^ｎ+1＋４^2ｎ-1 のとき、ａ_ｎ＝３・３^ｎ＋（１/４）・１６^ｎ として、

　ａ_ｎ+1＝９・３^ｎ＋４・１６^ｎ 、ａ_ｎ+2＝２７・３^ｎ＋６４・１６^ｎ

これを、３^ｎ、１６^ｎに関する連立方程式と考えて、

　３^ｎ＝（１６ａ_ｎ+1−ａ_ｎ+2）/１１７　、　１６^ｎ＝−（３ａ_ｎ+1−ａ_ｎ+2）/５２

これらを、ａ_ｎ＝３・３^ｎ＋（１/４）・１６^ｎ に代入して、

　ａ_ｎ＝３・（１６ａ_ｎ+1−ａ_ｎ+2）/１１７−（１/４）・（３ａ_ｎ+1−ａ_ｎ+2）/５２

すなわち、　３・１３・１６ａ_ｎ＝１６・（１６ａ_ｎ+1−ａ_ｎ+2）−３・（３ａ_ｎ+1−ａ_ｎ+2）　より

　３・１３・１６ａ_ｎ＝１６・１６ａ_ｎ+1−１３・ａ_ｎ+2−３・３ａ_ｎ+1＝１３・１９ａ_ｎ+1−１３・ａ_ｎ+2

よって、求める漸化式は、　４８ａ_ｎ＝１９ａ_ｎ+1−ａ_ｎ+2　より、ａ_ｎ+2−１９ａ_ｎ+1＋４８ａ_ｎ＝０

ここで、ａ₁＝１３　、ａ₂＝９１＝１３・７　より、ともに１３の倍数なので、漸化式より、

ａ₃も１３の倍数となり、帰納的に、すべてのｎについて、ａ_ｎは１３の倍数である

という解法が、Ｓ（Ｈ）さんの推奨されるものである。

例　ａ_ｎ＝２^ｎ-1＋３^3ｎ-2＋７^ｎ-1 のとき、ａ_ｎ＝（１/２）・２^ｎ＋（１/９）・２７^ｎ＋（１/７）・７^ｎ として、

　　ａ_ｎ+1＝２^ｎ＋３・２７^ｎ＋７^ｎ 、ａ_ｎ+2＝２・２^ｎ＋８１・２７^ｎ＋７・７^ｎ 、

　　ａ_ｎ+3＝４・２^ｎ＋２１８７・２７^ｎ＋４９・７^ｎ

　これを、２^ｎ、２７^ｎ、７^ｎに関する連立方程式と考えて、

　　２^ｎ＝（３７８ａ_ｎ+1−６８ａ_ｎ+2＋２ａ_ｎ+3）/２５０

　　２７^ｎ＝（１４ａ_ｎ+1−９ａ_ｎ+2＋ａ_ｎ+3）/１５００

　　７^ｎ＝（−５４ａ_ｎ+1＋２９ａ_ｎ+2−ａ_ｎ+3）/１００

　これらを、ａ_ｎ＝（１/２）・２^ｎ＋（１/９）・２７^ｎ＋（１/７）・７^ｎ に代入して、

　　ａ_ｎ＝（２５７/３７８）ａ_ｎ+1−（２/２１）ａ_ｎ+2＋（１/３７８）ａ_ｎ+3）

すなわち、　３７８ａ_ｎ＝２５７ａ_ｎ+1−３６ａ_ｎ+2＋ａ_ｎ+3　より、求める漸化式は、

　　ａ_ｎ+3−３６ａ_ｎ+2＋２５７ａ_ｎ+1−３７８ａ_ｎ＝０

　ここで、ａ₁＝５　、ａ₂＝９０＝５・１８　、ａ₃＝２２４０＝５・４４８　より、ともに５の倍数なので、

漸化式より、ａ₄も５の倍数となり、帰納的に、すべてのｎについて、ａ_ｎは５の倍数である


（コメント）　Ｓ（Ｈ）さんによれば、漸化式は「あっという間に」出来るとのことであるが、その
　　　　　　計算は、手計算ではかなりしんどかった．．．。


（追記）　令和３年１２月７日付け

　次の問題を考える。

　任意の奇数 ｎ に対し、 ５^ｎ−３^ｎ−２^ｎ は３０で割り切れることを示せ。

　いくつか実験をしておこう。入試問題では、このような実験は必須な手法である。解決の糸
口が見つかるかもしれない。

　ｎ＝１のとき、　５^ｎ−３^ｎ−２^ｎ＝５−３−２＝０　は明らかに３０で割り切れる。

　ｎ＝３のとき、　５^ｎ−３^ｎ−２^ｎ＝１２５−２７−８＝９０　は、３０で割り切れる。

　ｎ＝５のとき、　５^ｎ−３^ｎ−２^ｎ＝３１２５−２４３−３２＝２８５０　は、３０で割り切れる。

　　・・・・・・・・・・・・・・・・・・・・・・・

と計算したものの、解決の糸口は見えない。次に着目すべきは、３０の倍数ということは、

　　２の倍数　かつ　３の倍数　かつ　５の倍数

ということ。これらを順次調べればよい。

　５^ｎ−３^ｎ−２^ｎ＝（４＋１）^ｎ−（２＋１）^ｎ−２^ｎ　と変形すれば、２の倍数であることは自明で
あるが、このようなとき、合同式を利用するのが美しい。

　５^ｎ≡１　（ｍｏｄ　２）、　３^ｎ≡１　（ｍｏｄ　２）、　２^ｎ≡０　（ｍｏｄ　２）　なので、

　５^ｎ−３^ｎ−２^ｎ≡１−１−０＝０　（ｍｏｄ　２）　から、　５^ｎ−３^ｎ−２^ｎは、２の倍数である。

　同様にして、

　５^ｎ≡（−１）^ｎ　（ｍｏｄ　３）、　３^ｎ≡０　（ｍｏｄ　３）、　２^ｎ≡（−１）^ｎ　（ｍｏｄ　３）　なので、

　５^ｎ−３^ｎ−２^ｎ≡（−１）^ｎ−０−（−１）^ｎ＝０　（ｍｏｄ　３）　から、

　５^ｎ−３^ｎ−２^ｎは、３の倍数である。

また、

　５^ｎ≡０　（ｍｏｄ　５）で、ｎは奇数から、　３^ｎ≡−２^ｎ　（ｍｏｄ　５）　なので、

　５^ｎ−３^ｎ−２^ｎ≡０＋２^ｎ−２^ｎ＝０　（ｍｏｄ　５）　から、

　５^ｎ−３^ｎ−２^ｎは、５の倍数である。

　以上から、５^ｎ−３^ｎ−２^ｎは、３０の倍数である。



　　　以下、工事中！