オイラーのトーシェント定理（フェルマー＝オイラーの定理）

正確な主張と基本用語

形式的には、n≥1かつgcd(a,n)=1ならば、a^{φ(n)} ≡ 1 (mod n)である。gcd(a,n)=1という条件は不可欠である。aとnが共通因子をもつ場合、この合同式は成り立つとは限らない。記号≡は、法nに関する同値関係を示し、二つの整数の差がnの倍数であることを意味する。φ(n)は、各正整数nに対して定義されるトーシェント関数である。

短い歴史

この定理は、17世紀にピエール・ド・フェルマーがnが素数である特別な場合について最初に見いだした考えを拡張したものである。およそ1世紀後、レオンハルト・オイラーは、法nにおける剰余の性質を用いて、より一般的な結果とその証明を与えた。オイラーは命題を一般化し、より広い形の明快な証明も提示したため、この定理は一般にフェルマーとオイラーの両名にちなんで呼ばれる。

証明の考え方

標準的な証明の一つでは、法nでの乗法を、乗法群、すなわち可逆な法nの剰余類の集合上の演算として捉える。この集合はφ(n)個の要素をもつ。gcd(a,n)=1であるためaも可逆であり、各単元をa倍する操作はこの集合を置換する。乗算の前後で全単元の積を考えると、a^{φ(n)}に元の積を掛けたものは元の積に合同となる。そこでこの積を消去すれば、a^{φ(n)} ≡ 1 (mod n)が得られる。この議論で用いるのは、剰余と法nにおける可逆性の基本的な性質だけである。

例・用途・帰結

簡単な例で定理を確認できる。n=7（素数）のとき、φ(7)=6であり、7で割り切れない任意のaについてa^6 ≡ 1 (mod 7)となる。これはフェルマーの小定理である。n=8ではφ(8)=4であり、任意の奇数aはa^4 ≡ 1 (mod 8)を満たす。この定理は計算数論における多くのアルゴリズムの基礎であり、特に合成数を法とする冪乗計算がφ(n)で記述される性質に依存するRSAなどの公開鍵暗号で重要である。

実用上の帰結には、状況によって大きな指数をφ(n)を法として縮約する方法や、法nにおける乗法逆元を検査・構成するための手法が含まれる。ただし、より細かな縮約には、φ(n)の代わりにより小さいカーマイケル関数を用いることがある。この関数は、すべての単元aについてa^{λ(n)} ≡ 1 (mod n)となる最小の指数λ(n)を与える。

トーシェント関数の性質と関連事項

• トーシェント関数は乗法的である。mとnが互いに素なら、φ(mn)=φ(m)φ(n)である。
• 素数pとk≥1に対し、φ(p^k)=p^k−p^{k−1}=p^k(1−1/p)である。
• オイラーの定理にはgcd(a,n)=1が必要である。この条件が満たされなければ合同式は大きく破綻しうる。例えばnの倍数は法nで0であり、可逆ではない。
• フェルマーの小定理はnが素数の場合に当たる特別な場合であり、オイラーの定理の多くの証明はフェルマーの結果の証明を一般化している。

参考情報。証明、一般化、計算的側面をより深く学ぶには、初等数論の教科書やオンライン資料の参考文献が有用である。次に探究すべき基礎的な話題には、法nにおける乗法群の構造、カーマイケル関数、暗号プロトコルへの応用がある。

関連項目：数論の概要、互いに素、合同関係、オイラーのトーシェント関数、フェルマーの小定理、ピエール・ド・フェルマー、レオンハルト・オイラー。