前回に引き続き早稲田大学の問題からピックアップします。今回扱うのは、解き方を知っていると非常に有利になる整数問題です。
《問題》
次の条件を満たす整数$n$を$100$で割った余りを求めよ。$$n \leqq (5+2 \sqrt{5})^{2019}<n+1$$
（早稲田大学2019年 前期(商)大問１（４））
※問題文の表現を一部変更しています。
《考え方》
$(5+2 \sqrt{5})^{2019}$ の値を直接求めるのは難しそうですが、この種の問題にはとっておきの秘策があります。
$p=5+2 \sqrt{5}$ と置いて、$$p-5=2 \sqrt{5}$$と変形し、両辺正なので2乗して$$(p-5)^2=20$$ $$\therefore p^2-10p+5=0$$を得ます。2次方程式 $x^2-10x+5=0$ の解は $x=5 \pm 2 \sqrt{5}$ となるので、$q=5-2 \sqrt{5}$ と置くと$$\begin{cases} p+q=10 \\ pq=5 \end{cases}$$となります。
ここで$k$を非負整数とすると、$p^k+q^k$ は対称式なので基本対称式の $p+q$ と $pq$ によって表示できます。したがって、$p+q$ と $pq$ が整数なら $p^k+q^k$ も整数となることが分かります。また、$|q|<1$ のとき、$k$が十分に大きければ $p^k+q^k \approx p^k$ となるので、$p^k$ の値はほとんど整数に近い値になりそうです。
● ● ●
以上のことを踏まえて答えを求めてみましょう。求めたいのは$$n \leqq p^{2019}<n+1$$を満たす整数$n$を$100$で割った余りなので、まず $p^{2019}+q^{2019}$ について考えます。
$A_k=p^k+q^k$ と置くと、$$p^{k+2}+q^{k+2}=(p^{k+1}+q^{k+1})(p+q)-pq(p^{k}+q^{k})$$より、関係式$$A_{k+2}=10A_{k+1}-5A_{k}$$が成り立ちます。いま、$A_{k}$を$100$で割った余りを$r_{k}$と置くと、関係式$$r_{k+2} \equiv 10r_{k+1}-5r_{k} \pmod{100}$$が得られます（帰納法で証明可能）。
この関係式を用いて小さい方から$r_k$を書き出していくと、$p^0+q^0=2$、$p^1+q^1=10$ より、$r_0=2$、$r_1=10$ となるから、$$\begin{align} r_2 & \equiv 10r_1-5r_0 \pmod{100} \\ &=10 \cdot 10 -5 \cdot 2 \\ &=\color{orange}{90} \end{align}$$ $$\begin{align} r_3 & \equiv 10r_2-5r_1 \pmod{100} \\ &=10 \cdot \color{orange}{90} -5 \cdot 10 \\ &=850 \\ & \equiv \color{green}{50} \pmod{100} \end{align}$$ $$\begin{align} r_4 & \equiv 10r_3-5r_2 \pmod{100} \\ &=10 \cdot \color{green}{50} -5 \cdot \color{orange}{90} \\ &= \color{blue}{50} \end{align}$$ $$\begin{align} r_5 & \equiv 10r_4-5r_3 \pmod{100} \\ &=10 \cdot \color{blue}{50} -5 \cdot \color{green}{50} \\ &= 250 \\ & \equiv 50 \pmod{100} \end{align}$$…となります。これを同様に続けていけば$r_k$は $k \geqq 3$ のとき常に$50$となることが言えます。
したがって、$p^{2019}+q^{2019}$ を$100$で割った余りは$50$であり、$q^{2019}$は$1$より小さいので、整数$n$について$$n \leqq p^{2019}<p^{2019}+q^{2019}=n+1$$が成り立ちます。よって$n$を$100$で割った余りは $\color{red}{49}$ と求められます。
（コメント）
今回、解答の中で持ち出した $5-2 \sqrt{5}$ は、言ってみれば $5+2 \sqrt{5}$ に対して「共役」な形になっています。これを組にして考えることで、整数$n$の余りを間接的に求めることができました。この考え方は当サイトで公開している「創作整数問題#21」でも登場します。本問のように「相方」を考える方法は知っておいて損はありません。
$5-2 \sqrt{5}$ は$1$より小さい値をとるため、十分大きい$k$について $p^k+q^k \approx p^k$ となって議論が簡単でした。実際、$(5+2 \sqrt{5})^{2019}$ は小数点以下$560$桁まで「$9$」が続くような実数になっています。もしこれが $(7+2 \sqrt{5})^{2019}$ などの場合には別のアプローチが必要になりそうです。
（おまけ）
» $(5+2 \sqrt{5})^{2019}$の値
2807736652317738677566332338300380612333430316975465453574903193941847525934620443314875113486924245460016618954981657734093090697138207815338249229691166101343066618301283822502042599787230121641460586667304337915507507213791900272058074423673728783607456717840654291956114708186429707112414695793154292229571653482812386560924303091178359877384171774238359230902543793265401103282867194902809541422850076212489270004333852119937449136758140831146447080458847581472985652639050365697302011992468056097430267636408235538087544690471304894624863395112840271821678048019662468334872434243755990092573083885579523948932726523125707852487767472989900280647813726645071629732063332406153422953902353399641809770449820018345593721939905876712124845050461983275140752780932475524025037651286304070735272003858689670299413839148619375493403563004649518120639089182707127020877998755834708918905959376037585657872187846570070420967873935903691582463463865749047362771851285342670039935682993023829334554226137143619643784563472497948379874707326487756714163225731630284484163099258444016764538964214545360694470747611675748093832374277945669848079096680664666120262771887476300962657413301062633076891838003728970795551700374819336773352605171627149445592954378572677228598856284348222194834911768812843168499577135768284425695427458015843421545214975656723559654916511958128274818764491930454532307980472243637049299009111092469988295877907722454137929511629897005148964612038896044211033684858388934505009596547228238230481666676230545683437947467664305064436275730307004692677356092171895599872157752777719708749763886755221100985424581392076516257629075459671925235876439430042300624833398785361745301959867876909273535990542219364987984722865379687291759074962711526436953269670876980790436243953422003375462851475499564052989879751342077641136165579148068605262976009602419088452489538078427621828719573277933367249193036451703045551855919548245310579659417271614074707031249.9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999940832…
» 閉じる
（☝桁数多めなので注意！）