2016 年のカナダの Mathematical Olympiad Qualification(予選?)の問題を解きました。
問題概略
(1) が 11 の倍数となるような正の整数 をすべて求めよ。
(2) が 31 の倍数となるような正の整数 をすべて求めよ。
https://artofproblemsolving.com/community/c6h1259325p6529513
解説の pdf も作りました。きれいなレイアウトで読みたい方はこちらをどうぞ。
Fermat の小定理
Fermat の小定理から などが言えて(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)も解けますが,正直あまりやりたくないですね。
漸化式を作る
がみたす漸化式を作ります。4, 7, 20 を解にもつ 3 次方程式は
のとき などが成り立つので は次の漸化式をみたします。
これを で考えます。
この漸化式と , , から を 31 で割った余りが計算できます。
(2)の答えは「3 の倍数でない自然数」です。
(1)も同様に解けます。 とおくと
こちらはあまりメリットがなさそうです。, の剰余を直接求める方が速いでしょう。