巨大な数を割る話(証明編)
今回は前回の正統な続きです。軽く振り返ると、前回は次の問題を解きました。
しかし、そのために、オイラーの定理から得られるある等式を使用しました。その等式はまだ証明していなかったので、今回はその証明をしていきます。前回は証明なしの(不完全な)等式を利用しているので、「前回の記事を読んでいない!」という方は、むしろこの記事から読んだ方がいいかと思います(表記については前回の記事で触れてあります)。
まずはオイラーの定理とそのある等式をもう一度見てみましょう。AmodB=Cは「AをBで割った余りがC」ということを表し、M⊥Nは「MとNが互いに素である」ということを表します。
オイラーの定理については前回と少し表現を変えていますが、同じことです。そして例の等式については今回証明する過程で少しだけ条件を変えています。前回紹介した状態では条件が不十分だったのと、表現をシンプルにしたかったからです。
それでは、この命題を証明します。
以上が証明になります。見慣れない表現が多かったり、僕の表現が下手だったりして読むのが大変な方もいるかも知れませんが、頑張って読んでいただけると幸いです。
ただ、ここではすべてのqに対してm mod φ^(q)=1を条件としましたが、どうやらqとφ(p)さえmと互いに素であれば十分なようです。その場合の証明は下のようになります。
こちらの証明にはTwitterのフォロワーさんの一人に協力をいただきました。ありがとうございました。
おそらく、これで示せていると思います。実は、僕は最初から数学的帰納法で証明しようとしていたのですが、その誤りに気付くことができなかったため、方針を変えて一つ目の証明を行いました。数学的な厳密性は分かりませんが、個人的に式の途中を・・・で省略するのは嫌いです。なので、こちらの証明の方が好きです。
さて、こうやって二つの証明を書き、一つの疑問を持ちました。 上2つの証明で同じ等式を示しているのに条件が違うことから思いついたのですが、それだけでは証明に至らないはずです。ただ適当な整数pで実験する限り、成り立つ可能性は十分あると思いました。
まだ全然考察できていないので、これはまた別の記事にしたいと思います(証明出来たらですが)。もし読んで下さった方で証明を知っている方、思いついた方がいましたら、コメント欄などから教えていただけると幸いです。【追記】反例が見つかりました(p=47のとき)。上の証明で間違っている点があったら、そちらもよろしくお願いします。
ちなみに前回言っていた、2021 ↑² 2021を99で割った余りを求める別解はうまくいきませんでした。他によりスマートな答案はきっとあると思うので、ぜひ知りたいです。
今回は以上です。ありがとうございました。