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

はじめに

今回は前回の続きです。

目標

前回は定理 2-1 の唯一性を示しました。今回は存在性を示します。
定理 2-1 を再掲します。

定理 2-1 (逆元の存在とその唯一性)

\(2\) 以上の整数 \(n\) に対して、集合 \(\ZZ_n = \{0, 1, 2, \dotsc, n – 1\}\) を定義する。正の整数 \(a\) を \(n\) と互いに素な \(\ZZ_n\) の元 (要素) とするとき、$$ax \equiv xa \equiv 1 \pmod n$$をみたす \(x \in \ZZ_n\) がただ一つ存在する。

前回述べた通り、RSA 暗号を理解するためにストレートな証明を与えます。もし、「どうしてこれを思いついたのだろう?」と疑問が浮かんだ場合は、理由を考えてみてください。検索するとすぐに出てきます。他のウェブサイトにとても良い記事がありますので、ぜひ読んでみてください (具体的にどのページかは言えません)。

定理 2-1 の存在性の証明 (後編)

それでは定理 2-1 の存在性を証明していきましょう。

不定方程式

前回、ユークリッドの互除法を説明しましたが、具体例を挙げていませんでしたので、次の問題を解いてみましょう。

問題 2-2

整数 \(1120\), \(11\) の最大公約数 \(\gcd(1120, 11)\) を求めよ。

一瞬でわかってしまう人がいらっしゃるかと思いますが、ぜひユークリッドの互除法を使って求めてみてください。

問題 2-2 の解答

ユークリッドの互除法を適用し、\(\gcd(1120, 11)\) を求める。また、実数 \(x\) に対して、\(\lfloor x \rfloor\) を床関数とする。いま、\(a_0 = 1120,\) \(a_1 = 1120\) とおき、\(q_i = \lfloor a_{i – 1}/a_i\rfloor\)と定めると、\begin{align}
a_2 &= a_0 \bmod a_1 \\ &= a_0 – q_1a_1 \\ &= 1120 – 101\cdot 11 \\ &= 9, \\
a_3 &= a_1 \bmod a_2 \\ &= a_1 – q_2a_2 \\ &= 11 – 1\cdot 9 \\&= 2, \\
a_4 &= a_2 \bmod a_3 \\ &= a_2 – q_3a_3 \\ &= 9 – 4\cdot 2 \\&= 1, \\
a_5 &= a_3 \bmod a_4 \\ &= a_3 – q_4a_4 \\ &= 2 – 2\cdot 1 \\&= 0,
\end{align}よって、\(\gcd(1120, 11) = a_4 = 1\) である。

\(1120,\) \(11\) は互いに素な整数ということがわかりました。ユークリッドの互除法を逆から辿ると、次のような変形ができることがわかります。$$\begin{align}
\gcd(1120, 11) &= 1 \\
&= 9 – 4\cdot 2 \\
&= 9 – 4\cdot(11 – 1\cdot 9) \\
&= -4\cdot 11 + 5\cdot 9 \\
&= -4\cdot 11 + 5\cdot (1120 – 101\cdot 11) \\
&= 1120\cdot 5 + 11\cdot (-509)\end{align}$$整数の組 \((x, y) = (5, -509)\)は不定方程式 $$1120x + 11y = 1 = \gcd(1120, 11)$$の整数解の一つになります。前2式から方程式$$1120(x – 5) = -11(y + 509)$$が導けます。\(1120,\) \(11\) は互いに素な整数でしたので、\(x – 5\) は \(11\) の倍数、\(y + 509\) は \(1120\) の倍数です。したがって、\(k\) を整数とおくと、この不定方程式の一般解は$$x = 5 – 11k,\ \ y = -509 + 1120k$$となることがわかります。このようにして、ユークリッドの互除法により、不定方程式 \(ax + by = \gcd(a, b)\) の一般解 \((x, y)\) を求めることができます。

拡張ユークリッドの互除法

ユークリッドの互除法を拡張し、不定方程式 \(ax + by = \gcd(a, b)\) の解 \((x, y)\) の一つを求めるアルゴリズムを次に示します。これは拡張ユークリッドの互除法 (extended Euclidean algorithm) などと呼ばれています。

定義 2-4 (拡張ユークリッドの互除法)

正の整数 \(a,\) \(b\) \((a \geq b)\) を入力とする手続き \(P_2(a, b)\) を次のように定める。

1. \(a_0 \sets a,\) \(a_1 \sets b,\) \(x_0 \sets 1,\) \(x_1 \sets 0,\), \(y_0 \sets 0,\) \(y_1 \sets 1\) とおく。
2. \(a_{n + 1} = 0\) となるまで、次の処理を繰り返す。$$\begin{align}
q_i &\sets \lfloor a_{i – 1}/a_i\rfloor, \\
a_{i + 1} &\sets a_{i – 1} – q_ia_i = a_{i – 1} \bmod a_i, \\
x_{i + 1} &\sets x_{i – 1} – q_ix_i, \\
y_{i + 1} &\sets y_{i – 1} – q_iy_i\end{align}$$
3. \(a_n,\) \(x_n,\) \(y_n\) を出力する。

数列 \(\{a_i\}\) のみに着目すると、これは定義 2-3 の手続き \(P_1(a, b)\) すなわちユークリッドの互除法に一致します。数列 \(\{x_i\},\) \(\{y_i\}\) の意味は次の定理が説明してくれます。

定理 2-3

定義 2-4 の手続き \(P_2(a, b)\) において、整数 \(i \in \{0, 1, \dotsc, n + 1\}\) に対して、$$ax_i + by_i = a_i$$が成り立つ。

\(i = n\) を代入することで \(ax_n + by_n = a_n = \gcd(a, b)\) となり、解の存在を示せます。証明を次に示します。

定理 2-3 の証明

整数 \(i\) に関する数学帰納法により示す。\(i = 0,\) \(1\) のときは明らか。\(i = k – 1,\) \(k\) (\(k\) は \(n\) 以下の正の整数) に対して、題意が成り立つと仮定すると、$$\begin{align}
ax_{k+1} + by_{k+1} &= a(x_{k – 1} – q_kx_k) + b(y_{k – 1} – q_ky_k) \\
&= ax_{k-1} + by_{k-1} – q_k(ax_k + bx_k) \\
&= a_{k-1} – q_ka_k \\
&= a_{k+1}\end{align}$$となる。よって題意は示された。

これで不定方程式の解の存在を示せました。次に、拡張ユークリッドの互除法で得られる解の値の範囲を調べます。

定理 2-4

定義 2-4 の手続き \(P_2(a, b)\) において、\(d = \gcd(a, b)\) とおくと、$$|x_n| \leq \frac{b}{d},\ \ |y_n| \leq \frac{a}{d}$$が成り立つ。

誘導がないと少し難しいですので、まず次の問題を解くことにします。

問題 2-3

定義 2-4 の手続き \(P_2(a, b)\) において、次の問に答えよ。

(1)

\(n \geq i \geq 3\) のとき、\(|x_i| < |x_{i + 1}|,\) \(|y_i| < |y_{i + 1}|\) が成り立つことを示せ。

(2)

\(\gcd(|x_{n + 1}|, |y_{n + 1}|)\) を求めよ。

筆者は (2) の簡単な証明を探しています。

問題 2-3 の解答

(1)

\(n \geq 3\) のとき、\(q_i \geq 1\) だから、 
$$\begin{align}
x_2 &= x_0 – q_1x_1 \\ &= 1 – q_1\cdot 0 \\ &= 1, \\
x_3 &= x_1 – q_2x_2 \\ &= 0 – q_2\cdot 1 \\ &= -q_2, \\
x_4 &= x_2 – q_3x_3 \\ &= 1 – q_3(-q_2) \\ &= 1 + q_2q_3\end{align}$$となり、\(|x_3| < |x_4|\) をみたす。\(i \geq 3\) のとき、帰納的に$$\begin{align} |x_{i + 1}| &= |x_{i - 1} - q_ix_i| \\ &> |q_ix_i| \\ &\geq |x_i|
\end{align}$$となる。同様にして、\(n \geq i \geq 3\) のとき、\(|y_i| < |y_{i+1}|\) がいえる。

(2)

定理 2-3 より、整数 \(x_{n + 1},\) \(y_{n + 1}\) に対して \(y_{n+1}x – x_{n+1}y = \pm 1\) をみたす整数 \((x, y)\) が存在すれば、\(\gcd(|x_{n+1}|, |y_{n+1}|) = 1\) である (\(\gcd(|x_{n+1}|, |y_{n+1}|) = d > 1\) とおけば矛盾が導ける)。したがって、$$\begin{align}
y_{n+1}x_n – x_{n+1}y_n &= (y_{n-1} – q_ny_n)x_n – (x_{n-1} – q_nx_n)y_n \\
&= -(y_nx_{n-1} – x_ny_{n-1}) \\
&= y_{n-1}x_{n-2} – x_{n-1}y_{n-2} \\
&= \dotsm \\
&= (-1)^n(y_1x_0 – x_1y_0) \\
&= (-1)^n
\end{align}$$となる。よって、\(\gcd(|x_{n+1}|, |y_{n+1}|) = 1\) である。

さて、これを利用して 定理 2-4 を証明してみましょう。

定理 2-4 の証明

\(d = \gcd(a,b)\) とおく。定理 2-3 より、\(ax_{n+1} = -by_{n+1}\) となる。両辺を \(d\) で割って、$$\frac{a}{d}x_{n+1} = -\frac{b}{d}y_{n+1}$$を得る。\(\gcd(a/d, b/d) = 1\) であり、さらに、問題 2-3 (2) より \(\gcd(|x_{n+1}|, |y_{n+1}|) = 1\) であるから、$$|x_{n+1}| = \frac{b}{d},\ \ |y_{n+1}| = \frac{a}{d}$$となる。したがって、問題 2-3 (1) より、\(n \geq 3\) のとき、$$\begin{align}
|x_{n}| &< |x_{n+1}| = \frac{b}{d}, \\ |y_{n}| &< |y_{n+1}| = \frac{a}{d}\end{align}$$が成り立つ。\(n = 1\) のときは明らかに $$|x_n| \leq \frac{b}{d}, \ \ |y_n| \leq \frac{a}{d}$$となる。\(n = 2\) のとき、$$a = a_0 > a_1 > a_2 = d$$より、$$\begin{align}
|x_2| &= 1 \leq \frac{b}{d}, \\
|y_2| &= q_1 \\ &= \left\lfloor\frac{a_0}{a_1}\right\rfloor \\
&< \left\lfloor\frac{a}{d}\right\rfloor \\ &\leq \frac{a}{d}\end{align}$$ となる。よって、題意は示された。

もっと簡単に示せたら教えてください。

定理 2-1 の存在性の証明

最後に、定理 2-1 の存在性を示しましょう。ここまで来れば簡単です。

定理 2-1 の存在性の証明

ある整数 \(y\) を用いて、\(ax \equiv 1 \bmod n\) は$$ax + ny = 1$$と表わせる。定理 2-3, 2-4 より、この不定方程式をみたし、$$|x’| < n, \ \ |y'| \leq a$$となる整数の組 \((x, y) = (x', y')\) が存在する (\(n > a\) かつ \(\gcd(n, a) = 1\) より、ユークリッドの互除法の除算回数が \(2\) 回以上になるから \(x’\) の不等式に関して等号は成り立たない)。この不定方程式の一般解は整数 \(k\) を用いて、$$(x, y) = (x’ + nk, y’ – ak)$$と表わせる。\(x’ \geq 0\) のとき、\(x’ \in \ZZ_n\) である。\(x’ < 0\) のとき、\(x' + n \in \ZZ_n\) となる。よって、題意は示された。

長かったですが、証明できました。ここまでくどく詳しく書いてあるインターネット上のページは日本語ではないかもしれません。
最後に、1問問題を出して終わろうと思います。お疲れ様でした。

問題 2-4

\( 11x \equiv 1 \bmod 1120\) をみたす \(x \in \ZZ_{1120}\) が存在すれば求めよ。

答えは \(x = 611\) です。

次回予告

次回は「オイラーの \(\varphi\) 関数 (Euler’s totient funciton)」を扱うと思います: RSA暗号の数学 その4 オイラーのφ関数

この記事のキーワード

この記事の著者

ャに
記事一覧

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

 医学部合格実績を見る 

著者一覧