【必見‼】オイラーの定理(数論,合同式,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になりました。

    • tisikinohakotisikinohako より:

      すみません。重大なミスを犯してしまっていました。ご指摘ありがとうございます。こんな問題載せてほしいなどあったら連絡してくれると嬉しいです^^;

  3. カイ より:

    問題2の解説ですが、13^17≡1(mod1000)が唐突すぎてわかりません。それに13^17≡1(mod1000)は1ではなく933では?それと解答の17だと13^17≡13(mod24)になりますが。

    • tisikinohakotisikinohako より:

      コメントの通知設定をオフにしていたので、今まで気づきませんでした。こんなに返信が遅くなり申し訳ありません。
      間違いのご指摘ありがとうございます。自分で問題を作るって難しいですね。もし、間違いなどあればまたコメントしてください

プロフィール

この記事を書いた人
tisikinohako

このブログの情報が少しでも役に立てれば嬉しいです。