pencil創作整数問題#48解法&創作整数問題#49平成最後の大晦日を迎えますが、毎年恒例の渋谷駅前のカウントダウンは一段と盛り上がりそうです。は$2$以上の任意の整数$n$に対して整数にならないことを示せ。(創作問題)創作問題としてはいますが、かなり有名な問題だと思います。は$2$以上の任意の整数$n$に対して整数にならないことを示せ。閉じる創作整数問題#48(解き方)$48$進法における$5^n$の下2桁が$01$となるような最小の自然数$n$を求めよ。「下2桁」というのが意外に曲者だったのではないでしょうか。}$$を満たすような最小の自然数$n$を求めよ、ということになります。\pmod{10^2}$$となるときなので、$10$を$48$に変えれば$48$進法の場合になります。ある$n$について$5^n$を$48^2(=2^8\cdot3^2)$で割ったときの余りが$1$になるには、まず$5^n$を$3^2$、即ち$9$で割ったときの余りが$1$となる必要があります(必要条件による絞り込み)。\pmod{3}$$となるのは$n$が偶数のときです。あることから分かります。}$$を満たすような自然数$n$は$6$の倍数であることが分かりました。あることはすぐ計算できます。始めても良いのですが、$256$というのは法としてはやや大きい数なので上手く絞り込まなければ解の候補の数が膨れ上がってしまいます。\pmod{16}$$がすぐに分かりますので、自然数$n$は少なくとも$4$の倍数でなければなりません。絞り込んでみましょう。なって$1$にならないことを確認しています)。なって$1$にならないことを確認しています)。・・・そろそろ計算も面倒になって来るので、次の補題を示しておきましょう。となり成り立っている。\end{align}$$と計算できる。\pmod{2^{k+3}}$$が成り立つことが示された。\pmod{256}$がそれぞれ簡単に得られます。}$$を満たすような自然数$n$は$64$の倍数であることが分かりました。以上(1)と(2)の考察より、方程式$(\text{A})$を満たすような自然数$n$について、$6$の倍数かつ$64$の倍数、即ち$192$の倍数であることが必要十分なので、最小の自然数$n$は$$n=\color{red}{192}$$と求めることができます。(コメント)$48$進法ということで少し身構えてしまうかもしれませんが、要はmodの計算だけですね。$n$は$16$の倍数$\vdots$という仕組みになっているためです。\pmod{2^{k+2}}$$という関係式も帰納法で簡単に証明できますし、補題なんぞ示さずにひたすら計算してゴリ押すこともできます。冪の合同式について次の定理が知られています。b\pmod{n}$のとき、1つ目の括弧内は$n$で割り切れる。0\pmod{n}\end{align}$$となる。は$n^2$で割り切れる。した場合に相当します)。\pmod{48^2}$$を満たす$n$が$192$(の倍数)しか存在しない、ということまでは保証していません。\pmod{\color{red}{42}^2}$$を満たす$n$を求める際には利用できません。\pmod{42^2}$$を満たす最小の$n$は、その$7$倍の$42$であることが確かめられます。解答例で証明した補題は管理人が問題を解いているときに見つけたものなので、広く知られているものではないと思います・・・。良い別解もありそうな気がします。コメントをキャンセルメールアドレスが公開されることはありません。(2020/02/08記)風邪やウイルスが流行っていますね。手洗いうがいの励行と、良質な食事と睡眠を心掛けて生活しましょう!当サイトについてのご意見・ご要望はトップメニューバーの「その他」→「お問い合わせ」のページからお寄せ下さい。当サイトを閲覧するときはJavaScriptを有効化して下さい。スマートフォンの場合、ブラウザや機種、インターネット環境によってはMathjaxの立ち上がりにやや時間が掛かることがありますので、ご理解下さい。当サイトへのリンク付けは基本的に自由です。任意としますが、その際は管理人まで一声掛けて頂けると更新の励みになります。投稿記事・固定ページを含むすべての内容の著作権は当サイトに帰属します。当サイトの記事等の内容を引用する際は必ず出典とリンク(URL)を記載して下さい。