札幌の予備校・塾|大学受験(英語・数学)は札幌のマンツーマン個別指導塾、高上へお電話ください!大学受験において偏差値を上げる塾ですので、生徒の地力を底上げします。札幌駅、大通り駅にある予備校・塾のマンツーマン個別指導塾高上は、大学受験の英語、数学、物理、化学を静かな環境の個室で指導します。周りの声が邪魔になることはありません。英作文の添削、スカイプでの指導も全国どこからでも随時受け付けております。
お気軽にお問い合わせください。
TEL:080-1885-3972
受付時間:10:00~21:00
年中無休(相談などについては要予約)
※指導中はお電話に出られません。
お問い合わせページよりご連絡ください。
公開日:2021年2月14日
最終更新日:2021年5月17日

はじめに

前回前々回の記事で、拡張ユークリッドの互除法を用いて、集合 \(\ZZ_n = \{0, 1, 2, \dotsc, n – 1\}\) の \(0\) でない元 \(a \in \ZZ_n\) が \(n\) と互いに素のとき、$$ax \equiv xa \equiv 1 \pmod n$$となる \(x \in \ZZ_n\) がただ一つ存在することを証明しました (定理 2-1)。今後、そのような \(x\) を \(x = a^{-1}\) と書きます。
今回は「オイラーの \(\varphi\) 関数 (Euler’s totient function)」について説明し、このシリーズの最初に証明した「フェルマーの小定理」を一般化した「オイラーの定理 (Euler’s theorem)」を証明します。

準備

まず、表記の導入をします。集合の表記については、高校数学で一般的に使われるものを用いますが、集合 \(A\) に対して、\(|A|\) を元の個数とします。また、集合 \(A,\) \(B\) に対して、\(A \backslash B = A \cap \bar{B}\) とします。さらに、集合 \(\ZZ_n^*\) を \(n\) と互いに素な整数 \(k\) を用いて、$$\ZZ_n^* = \{k \bmod n \in \ZZ_n\backslash\{0\} \mid \gcd(n, k) = 1\}$$とします。

オイラーの \(\varphi\) 関数

準備ができましたので、オイラーの \(\varphi\) 関数を次に示します。

定理 3-1 (オイラーの \(\varphi\) 関数)

非負整数 \(n\) に対して関数 \(\varphi(n)\) を \(n\) と互いに素な \(n\) 未満の正の整数の個数、すなわち、$$\varphi(n) = |\ZZ_n^*|$$とする。この \(\varphi\) をオイラーの \(\varphi\) 関数 (Euler’s totient function) とよぶ。

例を示します。たとえば、\(n = 8\) のとき、$$\ZZ_{15}^* = \{1, 2, 4, 7, 8, 11, 13, 14\}$$より、\(\varphi(8) = |\ZZ_{15}^*| = 8\) です。

オイラーの \(\varphi\) 関数に関する諸性質

ここでは、オイラーの \(\varphi\) 関数が「乗法的」であることとオイラーの定理を証明します。RSA 暗号の仕組みを理解するだけであれば、オイラーの定理は必要ありませんが、せっかくなのでやっておきましょう。

乗法的関数

オイラーの \(\varphi\) 関数は次のような性質を持っています。

定理 3-1 (乗法的関数)

互いに素な正の整数 \(m,\) \(n\) に対して、$$\varphi(mn) = \varphi(m)\varphi(n)$$が成り立つ。

このような性質を持つ関数を乗法的関数 (multiplicative function)といいます。証明のために次の問題を考えます。

問題 3-1

\(m,\) \(n\) を互いに素な正の整数とすると、整数 \(a,\) \(b\) に対して、$$\begin{align}
x &\equiv a \pmod m, \\
x &\equiv b \pmod n
\end{align}$$となる整数 \(x\) が \(mn\) を法としてただ一つ存在する。

次に解答例を示します。

問題 3-1 の解答

\(\gcd(m, n) = 1\) だから、定理 2-3 より、$$mz + nw = 1$$となる整数 \((z, w)\) が存在する。両辺に \(a,\) \(b\) を掛けると$$\begin{align}
mza + nwa &= a, \\
mzb + nzb &= b
\end{align}$$となる。いま、\(x = nwa + mzb\) とおくと、$$\gcd(m, n) = \gcd(m, |w|) = \gcd(n, |z|) = 1$$より、$$\begin{align}
x &\equiv nwa \\
&\equiv 1\cdot 1\cdot a \\
&\equiv a \pmod m, \\
x &\equiv mzb \\
&\equiv b \pmod n
\end{align}$$となる。定理 2-2 より、$$\begin{align}
\gcd(x, m) &= \gcd(a, m) = 1, \\
\gcd(x, n) &= \gcd(b, n) = 1
\end{align}$$が成り立つから、\(\gcd(x, mn) = 1\) がいえる。いま、\(x\) の他に整数 \(x’\) も$$\begin{align}
x’ &\equiv a \pmod m, \\
x’ &\equiv b \pmod n
\end{align}$$をみたしているとすると、同様に \(\gcd(x’, mn) = 1\) が成り立つ。よって、\(\gcd(m, n) = 1\)より、\(x’ \equiv x \pmod{mn}\) がいえ、\(x\) は \(mn\) を法としてただ一つ存在することがわかる。

これを用いて、オイラーの \(\varphi\) 関数が乗法的であること (定理 3-1) を示しましょう。

定理 3-1 の証明

定義より、正の整数 \(n\) に対して、\(\varphi(n) = |\ZZ_n^*|\) であった。いま、\(\gcd(m, n) = 1\)とし、整数 \(x\) を 問題 3-1 をみたす \(x\) とすると、任意の \(a \in \ZZ_m^*,\) \(b \in \ZZ_n^*\) に対して、整数の組 \((a, b)\) から \(y = x \bmod mn \in \ZZ_{mn}^*\) への対応が一意に定まる。逆に、任意の \(y \in \ZZ_{mn}^*\) から \(a \in \ZZ_m^*,\) \(b \in \ZZ_n^*\) の組 \((a, b)\) への対応が、$$\gcd(m, n) = \gcd(y, m) = \gcd(y, n) = 1$$より、一意に定まる。したがって、\(a \in \ZZ_m^*,\) \(b \in \ZZ_n^*\) の組 \((a, b)\) と \(y \in \ZZ_{mn}^*\) は一対一に対応する。よって、$$\varphi(mn) = \varphi(m)\varphi(n)$$が成り立つ。

オイラーの定理

それでは、オイラーの定理 (Euler’s theorem) を次に示します。

定理 3-2 (オイラーの定理)

\(n\) を \(2\) 以上の整数とすると、任意の \(a \in \ZZ_n^*\) に対して、$$a^{\varphi(n)} \equiv 1 \pmod n$$が成り立つ。

オイラーの定理を証明するために、次の問題を解いてみます。

問題 3-2

(1)

任意の \(g \in \ZZ_n^*\) に対して、\(g^k \equiv 1 \pmod n\) となる非負整数 \(k \leq |\ZZ_n^*|\) が存在することを示せ。

(2)

任意の \(g \in \ZZ_n^*\) に対して、集合 \(G\) を$$G = \{g^i \bmod n\mid i\text{ は整数}\}$$とすると、\(|G|\) は \(|\ZZ_n^*|\) を割り切ることを示せ。

次に解答を示します。

問題 3-2 の解答

(1)

任意の正の整数 \(i\) に対して、\(\gcd(n, g^i) = 1\) だから、\(g^i \bmod n \in \ZZ_n^*\) となる。また、\(\ZZ_n^*\) は有限集合だからある整数 \(x,\) \(y\) \((x > y\)) が存在して、$$g^x \equiv g^y \pmod n$$が成り立つ。さらに、定理 2-1 より、\(g^y\) の逆元 \((g^y)^{-1} \equiv g^{-y} \pmod n \in \ZZ_n^*\) が存在する。したがって、$$g^x\cdot g^{-y} \equiv g^{x – y} \equiv 1 \pmod n$$となる。ここで \(k\) を \(k = x – y\) となる最小の正の整数とおけば、$$g^0, g^1, \dotsc, g^{k-1}$$は \(n\) を法としてすべて相異なることがわかる。よって、\(k \leq |\ZZ_n^*|\) となる。

(2)

(1) より、\(k \leq |\ZZ_n^*|\) である。\(k = |\ZZ_n^*|\) のときは明らか。\(k < |\ZZ_n^*|\) ならば、$$g^0, g^1, \dotsc, g^{k-1}$$と \(n\) を法としてすべて異なる \(g’ \in \ZZ_n^*\backslash G\) が存在し、$$g’g^0, g’g^1, \dotsc g’g^{k-1}$$は \(n\) を法として 上の \(g^i\) \((0 \leq i < k)\) を含めすべて相異なる (合同なものがあると仮定すると矛盾が生じる)。\(2k < |\ZZ_n^*|\) ならば、同様の操作を繰り返し、正の整数 \(l\) を用いて \(kl = |\ZZ_n^*|\) とすることができる。よって、\(|G|\) は \(|\ZZ_n^*|\) を割り切る。

問題 3-2 (2) は群論の「ラグランジュの定理 (Lagrange’s theorem)」の特殊ケースです。
これでオイラーの定理 (定理 3-2) を証明する準備が整いました。

定理 3-2 の証明

問題 3-2 より、\(a \in \ZZ_n^*\) だから、\(a^k \equiv 1 \pmod p\) となる正の整数 \(k \leq |\ZZ_n^*|\) が存在し、ある正の整数 \(l\) に対して、\(kl = |\ZZ_n^*|\) をみたす。よって、\(\varphi(n) = |\ZZ_n^*|\) より、$$\begin{align}
a^{\varphi(n)} &\equiv a^{|\ZZ_n^*|} \\
&\equiv a^{kl} \\
&\equiv (a^k)^l \\
&\equiv 1^l \\
&\equiv 1 \pmod n\end{align}$$が成り立つ。

\(p\) を素数とすると、\(\varphi(p) = p – 1\) より、オイラーの定理は$$a^{\varphi(p)} \equiv a^{p – 1} \equiv 1 \pmod p$$となり、最初の記事で証明したフェルマーの小定理に一致します。

次回予告

これで RSA 暗号の仕組みを理解する準備が整いました。公開鍵暗号方式について軽く説明し、RSA 暗号が正しく動くことを証明します。

この記事のキーワード

この記事の著者

ャに
記事一覧

高上は医学部合格率80%!
結果が出る指導を受けてみませんか?

 医学部合格実績を見る 

著者一覧