平野塾@吉祥寺

a^n + b^n + c^n の倍数判定（2016 カナダ予選）

数オリ

問題概略
Fermat の小定理
漸化式を作る

2016 年のカナダの Mathematical Olympiad Qualification（予選？）の問題を解きました。

問題概略

(1)　 $3^n + 4^n$ が 11 の倍数となるような正の整数 $n$ をすべて求めよ。
(2)　 $4^n + 7^n + 20^n$ が 31 の倍数となるような正の整数 $n$ をすべて求めよ。
https://artofproblemsolving.com/community/c6h1259325p6529513

解説の pdf も作りました。きれいなレイアウトで読みたい方はこちらをどうぞ。

drive.google.com

Fermat の小定理

Fermat の小定理から $3^{10}\equiv 4^{10}\equiv 1\pmod{11}$ などが言えて(1)(2)の式の剰余はそれぞれ 10, 30 を周期にもちます。

(1)程度なら 11 で割った余りを全パターン調べるのも簡単です。

\begin{array}{|c||c|c|c|c|c|c|c|c|c|c|}
\hline
n&1&2&3&4&5&6&7&8&9&10\\\hline\hline
\text{$3^n$の余り}&3&9&5&4&1&3&9&5&4&1\\\hline
\text{$4^n$の余り}&4&5&9&3&1&4&5&9&3&1\\\hline
\text{$3^n+4^n$の余り}&7&3&3&7&2&7&3&3&7&2\\\hline
\end{array}

この表から(1)は「解なし」であることがわかります。この方法で(2)も解けますが，正直あまりやりたくないですね。

漸化式を作る

$a_n=4^n+7^n+20^n$ がみたす漸化式を作ります。4, 7, 20 を解にもつ 3 次方程式は

$(t-4)(t-7)(t-20)=0\quad \therefore t^3-31t^2+248t-560=0$

$4^3-31\cdot 4^2+248\cdot 4-560=0$ のとき $4^{n+3}-31\cdot 4^{n+2}+248\cdot 4^{n+1}-560\cdot 4^n=0$ などが成り立つので $a_n$ は次の漸化式をみたします。

$a_{n+3}-31a_{n+2}+248a_{n+1}-560a_n=0$

これを $\bmod\,31$ で考えます。

$a_{n+3} =31a_{n+2}-248a_{n+1}+560a_n\equiv 2a_n$

この漸化式と $a_1\equiv 0$ , $a_2\equiv 0$ , $a_3\equiv 2$ から $a_n$ を 31 で割った余りが計算できます。

$a_{3k-2}\equiv 0,\, a_{3k-1}\equiv 0,\, a_{3k}\equiv 2^k\not\equiv 0\pmod{31}$

(2)の答えは「3 の倍数でない自然数」です。

(1)も同様に解けます。 $b_n=3^n+4^n$ とおくと

$b_{n+2}-7b_{n+1}+12b_n=0$

$\therefore b_{n+2}= 7 b_{n+1}-12b_n\equiv 7 b_{n+1}-b_n\pmod{11}$

こちらはあまりメリットがなさそうです。 $3^n$ , $4^n$ の剰余を直接求める方が速いでしょう。

variee.hatenablog.com