「初等整数論/原始根と指数」の版間の差分
削除された内容 追加された内容
初等整数論/フェルマーの小定理 oldid=108891 2016年12月16日 (金) 04:37 主執筆者 Polgoe, Angol_Moisから分割 |
初等整数論/合同の応用 oldid=108741 2016年12月6日 (火) 07:46 by Polgoe, 主執筆者 Angol Mois から分割 |
||
31 行
<math>{\rm lcm}(e, f) = l</math> とおくと、[[初等整数論/整除性#定理 1.5|定理 1.5]] より、<math>dl = ef \iff l = \frac{ef}{d} = e'f'</math> とおいて、<math>e' \, | \, e, f' \, | \, f, (e', f') = 1</math> とすることができる。 （※1）
<math>a^{\frac{e}{e'}}, b^{\frac{f}{f'}}</math> の位数はそれぞれ、定理 2.2.3 より <math>\frac{e}{\gcd (\frac{e}{e'}, e)} = e', \frac{f}{\gcd (\frac{f}{f'}, f)} = f'</math> である。（※2）
したがって、<math>(\frac{e}{e'}, \frac{f}{f'}) = 1</math> であることから、(i) より <math>a^{\frac{e}{e'}} b^{\frac{f}{f'}}</math> の位数は <math>e'f' = l={\rm lcm}(e, f)</math> となる。
80 行
====== 定理 2.
素数 <math>p</math> を法としての原始根の1つを <math>r</math> とおく。<math>\{1, r, r^2, \cdots, r^{p-2} \}</math> は剰余系である。また、どれも <math>p</math> と互いに素である（既約剰余系である）。特に <math>a</math> が <math>p</math> と互いに素な数であるとき <math>a\equiv r^l \pmod{p}</math> となる整数 <math>l (0\leq l\leq p-2)</math> が1つ定まる。
89 行
====== 定理 2.
<math>a</math> が <math>p</math> と互いに素な数とする。素数 <math>p</math> を法としての原始根の1つを <math>r</math> とし <math>k</math> を <math>a\equiv r^k \pmod{p} </math> となる整数とおくと <math>a\pmod{p}</math> の位数は <math>(p-1)/\gcd (p-1, k)</math> に等しい。
95 行
実際このとき[[初等整数論/整除性#定理 1.6'|定理 1.6']] より <math>a^e\equiv 1\pmod{p} \iff r^{ke}\equiv 1\pmod{p} \iff (p-1) \, | \, ke \iff (p-1)/\gcd(p-1, k) \, | \, e</math> である。
== 原始根・指数 ==
定理 2.3.1 で見たように法の素数を <math>p</math> とおき、<math>r</math> を原始根とすると、任意の <math>n</math> について
<math>r^a \equiv n \pmod{p}</math> となる <math>0 \leqq a < p-1</math> がただ一つ存在する。この <math>a</math> を 「<math>r</math> を底とする <math>n</math> の'''指数''' (index)」という。またこれを、次のように表記する。
<math>\mathrm{Ind}_r n = a</math> あるいは<math>\mathrm{log}_r n = a.</math>
定理 2.3.1 で見たように
:<math>a \equiv b \pmod{p} \iff \mathrm{Ind}_r a = \mathrm{Ind}_r b </math>
であることがわかる。
<math>p, r</math> をそれぞれ素数とその原始根とすると、
:<math>r^s \equiv n \pmod{p} \iff s \equiv \mathrm{Ind}_r \, n \pmod{p-1}</math>
であることがわかる。
次に見るように、指数は対数関数と類似した性質を持っている。それで、指数を<math>r</math> を底とする <math>n</math> の'''離散対数''' (discrete logarithm)と呼ぶこともある（古くから指数と呼ばれていたが、近年、暗号系への応用に伴って、離散対数問題として知られるようになった）。
====== 定理 2.3.3 ======
素数 <math>p</math> に対し <math>a, b</math> を <math>p</math> と互いに素な数、 <math>r, r'</math> を <math>p</math> を法とする原始根とすると、
<math>\begin{cases}
\mathrm{Ind}_r ab \equiv \mathrm{Ind}_r a + \mathrm{Ind}_r b, \\
\mathrm{Ind}_r a^n \equiv n \mathrm{Ind}_r a, \\
\mathrm{Ind}_{r'} a = \mathrm{Ind}_{r'} r \mathrm{Ind}_r a
\end{cases}
\pmod{p-1}.</math>
'''証明'''<br />
<math>\mathrm{Ind}_r a = \alpha, \mathrm{Ind}_r b = \beta</math> とおくと、定義より
<math>r^{\alpha} \equiv a, r^{\beta} \equiv b \pmod{p}</math> であるから
<math>ab \equiv r^{\alpha+\beta} \pmod{p}</math> がすぐに分かる。よって
:<math>\mathrm{Ind}_r \, ab \equiv \alpha + \beta \equiv \mathrm{Ind}_r \, a + \mathrm{Ind}_r \, b \pmod{p-1}</math>
ここから <math>\mathrm{Ind}_r a^n \equiv n \mathrm{Ind}_r a</math> は <math>n</math> に関する数学的帰納法で容易に証明される。
また <math>\mathrm{Ind}_r a = \alpha, \mathrm{Ind}_{r'} r = \rho</math> とおくと
<math>r^{\alpha} \equiv a, \ r'^{\rho} \equiv r \pmod{p}</math> より
<math>r'^{\rho \alpha} = (r'^{\rho})^{\alpha} \equiv r^{\alpha} \equiv a \pmod{p}</math> なので
<math>\mathrm{Ind}_{r'} a \equiv \rho \alpha \equiv \mathrm{Ind}_{r'} r \mathrm{Ind}_{r} a \pmod{p-1}</math> である。
== 原始根の応用例 ==
<math>p \neq 2, r</math> をそれぞれ素数とその原始根とする。
'''(1)''' <math>r^{\frac{p-1}{2}} \equiv -1 \pmod{p}</math> つまり <math>\mathrm{Ind}_r(-1) = \frac{p-1}{2}</math> である。
'''証明'''<br />
<math>(r^{\frac{p-1}{2}})^2 \equiv r^{p-1}\equiv 1 \pmod{p}</math> であるが
<math>x^2\equiv 1\pmod{p}</math> の解は <math>x\equiv \pm 1\pmod{p}</math> だから
<math>r^{\frac{p-1}{2}} \equiv \pm 1 \pmod{p}</math> がわかる。しかし
<math>r</math> は原始根であるから <math>r^{\frac{p-1}{2}} \not\equiv 1 \pmod{p}</math> なので
<math>r^{\frac{p-1}{2}} \equiv -1 \pmod{p}</math> でなければならない。
'''(2)''' <math>a+b = p</math> のとき <math>\mathrm{Ind}_r a - \mathrm{Ind}_r b \equiv \frac{p-1}{2} \pmod{p-1}</math>
'''証明'''<br />
実際 <math>a \equiv -b \pmod{p}</math> なので
:<math>\mathrm{Ind}_r a \equiv \mathrm{Ind}_r (-b) \equiv \mathrm{Ind}_r (-1)+\mathrm{Ind}_r b=\frac{p-1}{2}+\mathrm{Ind}_r b\pmod{p-1}</math>
である。
'''(3)''' <math>k</math> が <math>p-1</math> で割り切れないとき、
:<math>1^k + 2^k + 3^k + \cdots + (p-1)^k \equiv 0 \pmod{p}.</math>
'''証明'''<br />
原始根のべき乗は既約剰余系を成すので、この和は
:<math>\sum_{a=1}^{p-1} a^k \equiv \sum_{l=0}^{p-2} r^{lk}\pmod{p}</math>
となる。これを <math>r^k-1</math> 倍すると
:<math>(r^k-1)\sum_{a=1}^{p-1} a^k \equiv r^{(p-1)k} - 1\equiv 0</math>
となるが、<math>r</math> は <math>p</math> を法とする原始根だから <math>r^k \not\equiv 1</math> である。したがって、
:<math>\sum_{a=1}^{p-1} a^k \equiv 0</math>
となる。
また、原始根を[[初等整数論/合同式#ウィルソンの定理|ウィルソンの定理]]の別証明に用いることもできる。
:<math>(p-1)! \equiv r^0 r^1 r^2 \cdots r^{p-2} \equiv r^{0 + 1 + 2 + \cdots + (p-2)} \equiv (r^{\frac{p-1}{2}})^{p-2},</math>
ここで (1) より <math>r^{\frac{p-1}{2}} \equiv -1 \pmod{p}</math> なので
<math>(p-1)! \equiv (-1)^{p-2}</math>
となるが、<math>p</math> は奇素数なので、これは -1 に合同である。
また <math>(2-1)! = 1! = 1 \equiv -1 \pmod{2}</math> であるから、ウィルソンの定理が証明された。
== 原始根とべき剰余 ==
<math>x^n \equiv a \pmod{p}</math> が解を持つか、持たないかにしたがって <math>a</math> を <math>p</math> の <math>n</math> '''次剰余'''（べき剰余）、'''非剰余'''という。
べき剰余について、次の基本的な定理が成り立つ。
====== 定理 2.3.4 ======
<math>p</math> を素数、<math>a</math> を <math>p</math> で割り切れない数とする。<math>n\neq 0</math> を整数とし
<math>e=\gcd(n, p-1), f=(p-1)/e</math> とおく。
このとき次の3つはいずれも同値である。
* <math>x^n \equiv a \pmod{p}</math> が解を持つ。
* <math>e | \mathrm{Ind}_r a.</math>
* <math>a^f \equiv 1 \pmod{p}.</math>
またこのとき <math>x^n \equiv a \pmod{p}</math> の解の1つを <math>x_0</math> とすると、この合同方程式の解は
:<math>x_0r^{fl}, l=0, 1, \ldots e-1</math>
の <math>e</math>個である。
'''証明'''<br />
<math>r</math> を原始根とし <math>k=\mathrm{Ind}_r a</math> とおく。
<math>t=n/e</math> とおくと <math>\gcd(t, f)=1</math> より <math>tu\equiv 1\pmod{f}</math>
となる整数 <math>u</math> が存在する。
第一に <math>e | k</math> ならば <math>x=r^{ku/e}</math> は解である。実際
:<math>x^n=(r^{ku/e})^n=r^{kun/e}=r^{ktu}</math>
となるが
<math>(p-1) | ef | kf | k(tu-1)</math> より <math>ktu\equiv k\pmod{p-1}</math> だから
:<math>x^n=r^{ktu}\equiv r^k\equiv a\pmod{p}.</math>
第二に <math>x^n \equiv a \pmod{p}</math> ならば <math>nf=n(p-1)/\gcd(n, p-1)=(p-1)t</math> より
<math>a^f\equiv x^{nf}\equiv 1\pmod{p}</math> である。
第三に <math>a^f\equiv 1\pmod{p}</math> とする。<math>r</math> を原始根とし <math>k=\mathrm{Ind}_r a</math> とおくと
<math>r^{kf}\equiv 1\pmod{p}</math> つまり <math>(p-1) | kf</math> であるから
<math>e=(p-1)/f | k </math> である。
さて <math>x^n \equiv a \pmod{p}</math> の解が存在するとして <math>x_0=r^m</math> を解の1つとする。
このとき [[初等整数論/整除性#定理 1.6'|定理 1.6']] より
:<math>r^{sn}\equiv 1\pmod{n} \iff (p-1) | sn \iff f | s</math>
であるから
:<math>(x_0r^s)^n\equiv a \iff ar^{sn}\equiv a \iff f | s</math>
となる。 <math>ef=p-1</math> より解は
<math>x_0r^{fl}, l=0, 1, \ldots e-1</math>
の <math>e</math> 個である。
このことから、<math>e=\gcd (n, p-1)</math> とおくと <math>x^n \equiv a \pmod{p}</math> が解を持つことと <math>x^e \equiv a \pmod{p}</math> が解を持つことは同値であることがすぐにわかる。
よって、べき剰余を考える上では、 <math>n</math> が <math>p-1</math> の約数のときが本質的であると言える。
<math>n>1</math> が <math>p-1</math> の約数のとき <math>n</math> 次剰余は原始根ではない。なぜなら
<math>a^{(p-1)/n}\equiv 1\pmod{p}</math> より <math>a</math> の位数は <math>p-1</math> より小さくなるからである。
べき剰余については、後に[[初等整数論/べき剰余]]で詳しく考察する。
{{DEFAULTSORT:しよとうせいすうろん けんしこんとしすう}}
| |||