【必見‼】オイラーの定理(数論,合同式,mod)とその証明 練習問題付き‼‼

スポンサーリンク

初めに

オイラーの定理とその証明について解説していきたいと思います。wikipediaなどの証明を読んでもわからないという方にお勧めです。では見ていきましょう。

オイラーの定理とは

まず、オイラーの定理とは下のようなものです。

nが正の整数でaをnと互いに素な正の整数としたとき,

a^{\varphi (n)} \equiv 1 \pmod{n}

が成立する。(aの乗数のところはn以下のnと互いに素な自然数の数)

オイラーの定理の証明

では証明します。基本はwikipediaのものに補足するような形になっています

nと互いに素なn以下の正の整数の集合を
A=\{b_1,b_2,...,b_{\varphi(n)}\}
とします。

この要素のそれぞれにaをかけた集合
B=\{ab_1,ab_2,...,ab_{\varphi(n)}\}

を考えればaとnは互いに素だから、(同じものが1つも存在しない。)集合A,Bは法をnとしたときに一致し、当然その積も法nにおいて等しくなります。すなわちAの要素の積をPとすれば、P\equiv a^{\varphi(n)}P\pmod{n}

nとPは互いに素だから
a^{\varphi(n)}\equiv 1\pmod{n}
とわかります。

確かめ問題

簡単な例題を用意したので、ぜひ解いてみてください。

問題1

7400の下3桁をもとめよ。

問題1 解答・解説

この方法をしらない方は、二項定理でごちゃごちゃやったり規則性でごり押しするしかないわけですが、この方法を知っていると、簡単です。

まず、下3桁といわれているので、mod1000に注目します。

すると、1000と7は互いに素なので、先ほどのオイラーの公式を使うことができます‼‼

よって、1000と互いに素である数の個数は2の倍数でもなく5の倍数でもない数の個数なので、400と分かります。

なので、7400≡1(mod1000)となります。

よって、下一桁は1です。

終わりに

いかがでしたか。これを応用すると、いろいろな問題が簡単に解けるようになりますね。

もっと難しい応用例として数学オリンピックの問題があるので、ぜひ解いてみてください。(問9、下リンク)

また、ほかにも面白い記事をたくさん投稿していますので、そちらのほうも読んでいただければ光栄です。

  1. オクダ より:

    問題1について
    確かめてないからわからないですが、985と1000は互いに素ではないので
    やるなら、7^983≡1(mod1000)で
    7^4=2401
    で401じゃないですか?

  2. オクダ より:

    勘違いしていました。
    φ(n)はn以下の互いに素の数ではなく個数だったんですね。
    つまり
    φ(1000)=400
    7^987≡7^187≡1(mod1000)
    で以下のURLを参考にとくと
    https://smile2001x.exblog.jp/30070642/
    643になりました。

プロフィール

この記事を書いた人
tisikinohako

13歳から為替をはじめ、最近はAIを使って自動化するために、pythonを勉強中。

為替は、参考書やバイブルなどは一切読まず、基本エクセル分析だけで勝ってきました。

数学はフーリエ変換や、ベクトル解析など解析学を勉強中。

TwitterやYoutubeではめちゃくちゃすべったので、ブログで挽回しようと始めた結果、なんかうまくいったっぽいので続けてます。

このブログを応援していただければ光栄です。