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

初めに

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

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

nが正の整数でaを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}$
とわかります。

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

7⁴⁰⁰の下3桁をもとめよ。

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

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

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

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

なので、7⁴⁰⁰≡1(mod1000)となります。

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

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

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

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