オイラーの定理 (数論)

オイラーの定理

数論の分野に位置づけられるオイラーの定理は、初等整数論の中でも特に重要な理論の一つです。この定理は、互いに素な整数に関する特別な性質を明らかにし、数の性質を深く理解するための基盤となります。オイラーの定理によれば、正の整数$n$と$n$と互いに素な正の整数$a$があるとき、次の関係が成り立ちます。

$$
a^{ ext{φ}(n)} ext{ ≡ } 1 ext{ (mod n)}
$$

ここで、$ ext{φ}(n)$はオイラーのφ関数を表し、これは$n$以下の自然数の中で、$n$と互いに素な数の個数を示す関数です。

このオイラーの定理は、フェルマーの小定理を一般化したものであり、更にこの定理を発展させたものがカーマイケルの定理です。

証明の概要

オイラーの定理の証明は、まず$n$と互いに素な正の整数の集合を次のように定義します。

$$
A = ig\{ b_1, b_2, \ldots, b_{ ext{φ}(n)} \big
$$

この集合$A$の各要素に対して$a$を乗じた新しい集合$B$を考えます。

$$
B = \{ a b_1, a b_2, \ldots, a b_{ ext{φ}(n)} \}
$$

$a$と$n$が互いに素であるため、この2つの集合$A$と$B$は法$n$において同じ結果を持ちます。それゆえ、両者の要素の積も法$n$で同じ結果となります。

もし$A$の要素の積を$P$とすると、次のような関係が成り立ちます。

$$
P ≡ a^{ ext{φ}(n)} P ext{ (mod n)}
$$

$n$と$P$が互いに素であるため、これが成り立つように、次のことが言えます。

$$
a^{ ext{φ}(n)} ≡ 1 ext{ (mod n)}
$$

これにより、オイラーの定理が証明されます。

実例

オイラーの定理を用いた具体例として、$7^{2009}$の末尾2桁を求める方法を考えてみましょう。

まず、$100$に対するオイラーのφ関数を計算します。この場合、$ ext{φ}(100) = 40$となります。

次に、オイラーの定理を適用すると次のように表記できます。

$$
7^{40} ≡ 1 ext{ (mod 100)}
$$

したがって、$7^{2009}$は次のように変形されます。

$$
7^{2009} = 7^9 imes (7^{40})^{50}
$$

オイラーの定理により、$(7^{40})^{50} ext{ ≡ } 1$ですので、最終的には次のようになります。

$$
7^{2009} ≡ 7^9 ext{ (mod 100)}
$$

この計算から得られる結論は、$7^9 ext{ ≡ } 7 ext{ (mod 100)}$であり、したがって$7^{2009}$の下2桁は07となります。

関連項目

オイラーの定理は、レオンハルト・オイラーの名に由来し、数論の他の多くの分野にも関連しています。この定理の話題は、数の構造や秘密の通信、暗号学など、現代の数学や技術においても幅広く応用されています。

もう一度検索