ファイ関数とオイラーの定理 - ちりもつもればミルキーウェイ

はじめに

これは RSA完全理解 Advent Calendar の13日目の記事です

RSAの証明は以前フェルマーの小定理を用いてやりましたが、オイラーの定理を利用した証明も多いです。

勉強やりはじめると、理解のために肌に合う証明を探し求めたりすると思うので、ファイ関数とオイラーの定理についても紹介します

オイラーのファイ関数

トーシェント関数とも呼びます。 $\phi (n)$ みたいに書きます。

これはなにかというと $n$ 以下の値で $n$ と互いに素な数の個数を数え上げる処理です。概念としてはシンプルですね。ちなみに計算方法は

$\displaystyle n \prod_{i=1}^{k} (1 - \frac 1 {pi})$

です。 $n$ 素因数について $1 - \frac 1 {pi}$ で総乗して $n$ でかけると出てきます。

これは直感的にもただしいとわかります。なぜなら、素因数とその倍数は $n$ と互いに素でないのでカウントされないからです。そしてその登場頻度は $\frac 1 {pi}$ です。それを取り除く処理をすべての素因数について適用するだけということですね。

オイラーの定理

オイラーは多面体定理とかいろんな定理を出してるので、整数論に関する定理のことは区別してオイラーの定理(整数論)とかつけたりします。文脈から自明な場合はとくに断りをいれない事が多いです。以降は単にオイラーの定理といいます

さてオイラーの定理とは

オイラーの定理:

$n$ と $a$ が互いに素なとき $a^{\phi (n)} \equiv 1\pmod n$ がなりたつ

となる定理のことです。みるとわかりますが、これはフェルマーの小定理の一般化になっています。(フェルマーの小定理は法が素数 $p$ でないといけなかったが、オイラーの定理では単に互いに素なら適用できる)

オイラーの定理の証明

1以上 $n$ 以下の $n$ と互いに素な数について $S = \lbrace m_1, m_2, m_3, \cdots m_{\phi (n)} \rbrace$ とします。これらの要素はすべて $n$ 以下です。
これらをすべて $a$ でかけて $S' = \lbrace am_1, am_2, am_3, \cdots am_{\phi (n)} \rbrace$ とします。

このとき $S'$ の集合の要素をそれぞれ $n$ で剰余をとるとすべて異なります。
仮に剰余が等しい場合を仮定すると $am_i \equiv am_j\pmod n$ となります。
$a$ は両辺と互いに素なので割ると $m_i \equiv m_j\pmod n$ となり集合 $S$ 内の2要素の剰余が等しいことになり前提と矛盾します