合同式の乗算とべき乗

合同式の乗算とべき乗

 再び法 $7$ による剰余類を並べてみます。
 
\[\begin{align*}&C_0\,\{\:\cdots\:-14,\:-7,\:0,\:7,\:14,\:\cdots\:\}\\[6pt]
&C_1\,\{\:\cdots\:-13,\:-6,\:1,\:8,\:15,\:\cdots\:\}\\[6pt]
&C_2\,\{\:\cdots\:-12,\:-5,\:2,\:9,\:16,\:\cdots\:\}\\[6pt]
&C_3\,\{\:\cdots\:-11,\:-4,\:3,\:10,\:17,\:\cdots\:\}\\[6pt]
&C_4\,\{\:\cdots\:-10,\:-3,\:4,\:11,\:18,\:\cdots\:\}\\[6pt]
&C_5\,\{\:\cdots\:-9,\:-2,\:5,\:12,\:19,\:\cdots\:\}\\[6pt]
&C_6\,\{\:\cdots\:-8,\:-1,\:6,\:13,\:20,\:\cdots\:\}\end{align*}\]
 たとえば $C_2$ から $16$, $C_3$ から $3$ という要素を抜き出して掛け合わせてみると
 
\[16\times 3=48\in C_6\]
となります。あるいは $C_2$ から $9$, $C_3$ から $10$ という要素を抜き出して乗じてみても
 
\[9\times 10=90\in C_6\]
となります。これは決して偶然ではなく、$C_2,\:C_3$ からどのような数を抜き出して掛け合わせても必ず $C_6$ の要素となります。一般に法 $m$ のもとで $C_a,\:C_b$ から適当な数を抜き出して掛け合わせると、それらの数は全て合同となります(同じ類の元となります)。

[定理 C3] $a_1\equiv a_2,\:\:b_1\equiv b_2\:(\mathrm{mod}\;m)$ ならば、
\[a_1\,b_1\equiv a_2\,b_2\:(\mathrm{mod}\;m)\]

[定理 C3 の証明]
 $a_2=a_1+ms,\:\:b_2=b_1+mt\:(s,t\in\mathbb{Z})$ と書けるので、
 
\[\begin{align*}a_1\,b_1&=(a_1+ms)(b_1+mt)\\[6pt]
&=a_1\,b_1+m(a_1\,t+b_1\,s+st)\equiv a_1\,b_1\:(\mathrm{mod}\;m)
\end{align*}\]
となります。(証明終)

 加算の時と同じように、乗算においても普通の ("=" で結ばれた) 等式のように、(法 $m$ が共通していれば)辺々を掛け合わせることが許されるということです。たとえば
 
\[13\equiv 22,\quad 8\equiv 17\:(\mathrm{mod}\;m)\]
が成立しているので、辺々を掛けると左辺と右辺はそれぞれ
 
\[\begin{align*}13\times 8=104\equiv 2\:(\mathrm{mod}\;m)\\[6pt]
22\times 17=374\equiv 2\:(\mathrm{mod}\;m)\end{align*}\]
となって合同であることがわかります。
 

合同式のべき乗

 法 7 による剰余類 $C_2$ を再掲します。
 
\[C_2\,\{\:\cdots\:-12,\:-5,\:2,\:9,\:16,\:\cdots\:\}\]
 $C_2$ から $2$ と $-5$ を取り出して、それぞれ 2 乗すると $4,\:25$ となり、それぞれ $7$ で割ると $4$ が余るので $C_4$ の元となります。
 
\[4,\:25\in C_4\]
また、$2$ と $-5$ をそれぞれ 3 乗すると
 
\[8,\:-125\in C_1\]
となって、やはり 2 数は同じ類の元となります。このように、ある剰余類から 2 数を取り出してべき乗すると、それぞれ一緒に同じ類に移ります(合同関係が維持されます)。

[定理 C4] $a_1\equiv a_2\:(\mathrm{mod}\;m)$ ならば、
\[a_1^n\,\equiv\,a_2^n\:(\mathrm{mod}\;m)\quad n\in\mathbb{N}\]

 ここで $\mathbb{N}$ は自然数の集合を表しています。

[定理 C4 の証明] 数学的帰納法を用いて証明します。$n=1$ のとき
 
\[a_1\equiv a_2\:(\mathrm{mod}\;m)\]
が成り立っています。$n=k-1$ のとき
 
\[a_1\,^{k-1}\equiv a_2\,^{k-1}\:(\mathrm{mod}\;m)\]
が成り立つことを仮定すると、定理 C3(合同式の乗算)より
 
\[a_1\,^{k-1}\,a_1\,\equiv a_2\,^{k-1}\,a_2\:(\mathrm{mod}\;m)\]
 すなわち
 
\[a_1^k\,\equiv\,a_2^k\:(\mathrm{mod}\;m)\]
が成り立ちます。よって任意の自然数 $n$ について
 
\[a_1^n\,\equiv\,a_2^n\:(\mathrm{mod}\;m)\quad n\in\mathbb{N}\]
が成り立ちます。(証明終)
 
 たとえば $3\equiv 7\:(\mathrm{mod}\;4)$ が成り立っているので、両辺を 2 乗、3 乗, ... していっても合同関係は維持されるということです。
 
\[\begin{align*}3^2\equiv 7^2\:(\mathrm{mod}\;4)\\[6pt]
3^3\equiv 7^3\:(\mathrm{mod}\;4)\\[6pt]
3^4\equiv 7^4\:(\mathrm{mod}\;4)\\[6pt]
\cdots\cdots\cdots\cdots\cdots\end{align*}\]
 本当に成り立っているかどうか気になる場合は、Excel の MOD 関数などで実際に計算させて確認してください。

 ≫ 9 去法と 11 去法 ≫ 初等整数論入門講座

スポンサーリンク
スポンサーリンク
末尾広告
末尾広告

コメントをどうぞ

メールアドレスが公開されることはありません。

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください