フェルマー・オイラーの定理

フェルマー・オイラーの定理はフェルマーの小定理の拡張と考えてください。

フェルマー・オイラーの定理

( a,n ) = 1 ならば aφ(n) ≡ 1 ( mod n )　…(*)

ここで、( a,n ) とは、a と n の最大公約数をあらわし、それが１であるということは、a と n が互いに素であるということです。

またφ(n)はオイラー関数といい、n より小で n と互いに素な自然数の個数をあらわします。

ここで n が素数 p の場合、p より小の自然数で p と互いに素な自然数は、１から(p-1)のすべてなので、

φ(p) = p - 1

となります。このとき特に、(*)の定理をフェルマーの小定理といいます。

ではその拡張形、フェルマー・オイラーの定理を考えましょう。これは、１６４０年にフェルマー(Pierre de Fermat 1601-1665)がフェルマーの小定理を述べたあと、１７６０年にオイラー(Leonhard Euler 1707-1783)が拡張したものです。

・n で割って i 余る数を

( i : mod n)　　( i = ０、１、２、３、…、n-1)

とあらわし、mod n に関する i の剰余類（合同類）といいます。

例）　( 3 : mod 7) = {…、-11 、-4 、3、10、17、…}

また特に

( i,n ) = 1

のとき mod n の既約類といいます。

例）n = 12、a = 7 の場合を考えてみましょう。

12より小さい自然数は（１、２、３、４、５、６、７、８、９、１０、１１）で赤字は12の約数、下線は12と互いに素な自然数をあらわしています。

φ(12) = 4

a^φ(n) = 7⁴ = 2401 ≡ 1 (mod 4)//

確かに(*)は成り立ちます。

ここで mod 12 の既約類を並べてみましょう。

( 1 : mod 12)、( 5 : mod 12)、( 7 : mod 12)、( 11 : mod 12)

この１、５、７、１１に a = 7 をかけたものを並べると、

( 7・1 : mod 12) = ( 7 : mod 12)

( 7・5 : mod 12) = ( 11 : mod 12)

( 7・7 : mod 12) = ( 1 : mod 12)

( 7・11 : mod 12) = ( 5 : mod 12)

つまり、mod 12 の既約類に１２と互いに素である数７をかけても（順番は替わるけど）、やはり、mod 12 の既約類になります。

したがって、

(7・1)・(7・5)・(7・7)・(7・11) ≡ 1・5・7・11 ( mod 12)

１、５、７、１１はそれぞれ１２と互いに素なので、両辺を1・5・7・11で割れば、

7⁴ ≡ 1 ( mod 12 )

となり、7⁴の４は１、５、７、１１の個数、

φ(12) = 4

をあらわしています。

以上で、フェルマー・オイラーの定理を証明したわけではないですが、例から何となく理解していただけたのではないでしょうか？

TOP PAGE