合同式の真骨頂 (JMO 2018年 第4問)

 今回は2018年の数オリ予選から、特に印象に残っていた1問を紹介します。問題文は僅か1行で、問われている内容は極めてシンプルです。

 先日紹介した2020年の一橋入試(https://matsubushi.com/2020/03/01/2020年と割り算-2020年-一橋大学-数学/)と同様に、巨大な数をそれなりに大きな数で割った余りに関する問題です。

 11112018という値は10の累乗などと比べても扱いづらく、一橋大の時のように余りの周期性を考えようにもこのままでは2乗を計算するだけでも一苦労です。そこで、合同式に活路を見出してみます。

(解答)

 解答はわずか4行ですが、答えに至るにはそれなりに試行錯誤が要求されます。試しに1111≡-10000 (mod 11111)を適用してみると、値こそ大きくなりますが扱いが容易な10の累乗に関する余りの問題に帰着され、若干ながら光が見えてきます。

 そこで10の累乗を小さい順に11111で割ってみて、105を11111で割った余りが1であることに気が付けば本問は解決したも同然です。あとは合同式を用いた字数下げにより、11112018という巨大な数を計算することなく余りが求まります。

 一見解答不可能な計算問題もアイデア一つであっさり解けるという、数オリの醍醐味を感じるそんな一問です。

投稿者: matsubushi

趣味で数学など

合同式の真骨頂 (JMO 2018年 第4問)」に2件のコメントがあります

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Google フォト

Google アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中

%d人のブロガーが「いいね」をつけました。