初等整数論/原始根と指数
原始根

フェルマーの小定理によると、素数 p {\displaystyle p} とそれに互いに素な数 a {\displaystyle a} について、 a p − 1 ≡ 1 ( mod p ) {\displaystyle a^{p-1}\equiv 1{\pmod {p}}} だった。
原始根

また位数の法則によれば、位数は p − 1 {\displaystyle p-1} の約数だった。そこで、位数が p − 1 {\displaystyle p-1} になる数 a {\displaystyle a} を、「 p {\displaystyle p} (を法として)の原始根」という。
原始根

例えば、 2 3 ≡ 1 ( mod 7 ) {\displaystyle 2^{3}\equiv 1{\pmod {7}}} なので、2 は 7 の原始根ではない。
原始根

3 1 ≡ 3 , 3 2 ≡ 2 , 3 3 ≡ 6 ( mod 7 ) {\displaystyle 3^{1}\equiv 3,3^{2}\equiv 2,3^{3}\equiv 6{\pmod {7}}} なので、3 は 7 を法としての原始根である。(位数の法則より位数の可能性のあるものは 7-1 = 6 の約数、1, 2, 3, 6)
原始根

さて、原始根が存在することを証明しなければならない。 a {\displaystyle a} を p {\displaystyle p} で割り切れない任意の数とする。 a {\displaystyle a} の位数を e {\displaystyle e} とおく。すなわち、 a 0 , a 1 , a 2 , ⋯ , a e − 1 ≢ 1 ( mod p ) ⋯ ( 1 ) {\displaystyle a^{0},a^{1},a^{2},\cdots ,a^{e-1}\not \equiv 1{\pmod {p}}\cdots (1)} である。
原始根

位数に関する命題より合同方程式 X e ≡ 1 ( mod p ) ⋯ ( 2 ) {\displaystyle X^{e}\equiv 1{\pmod {p}}\cdots (2)} の解は a 0 ≡ 1 , a 1 , a 2 , ⋯ , a e − 1 {\displaystyle a^{0}\equiv 1,a^{1},a^{2},\cdots ,a^{e-1}} で尽くされる。
原始根

さて、 e = p − 1 {\displaystyle e=p-1} ならば証明は終了する。また位数の法則によって、 e ≦ p − 1 {\displaystyle e\leqq p-1} だから、 e < p − 1 {\displaystyle e<p-1} であったとしよう。そうすると、 p {\displaystyle p} で割ったときの余りは p {\displaystyle p} 種類なのだから、(1) のどれとも合同でない数 b {\displaystyle b} が存在する。また、特にこのとき、 e < p − 1 {\displaystyle e<p-1} なので、 p {\displaystyle p} で割り切れないような b {\displaystyle b} が取ってこれる。もちろん b {\displaystyle b} は定め方から (2) の解とはなり得ない。したがって、位数を f {\displaystyle f} とおいて、 b f ≡ 1 ( mod p ) {\displaystyle b^{f}\equiv 1{\pmod {p}}} とすると、 f {\displaystyle f} は e {\displaystyle e} の約数たりえない。もちろん、 f > 1 {\displaystyle f>1} である。
原始根

ここで、次のようにして a b {\displaystyle ab} の位数は a {\displaystyle a} の位数より大きいことが示される。
原始根

(i) ( e , f ) = 1 {\displaystyle (e,f)=1} のとき
原始根

a b e f = a e f b e f = ( a e ) f ( b f ) e ≡ 1 ( mod p ) {\displaystyle ab^{ef}=a^{ef}b^{ef}=(a^{e})^{f}(b^{f})^{e}\equiv 1{\pmod {p}}}
原始根

( a b ) x ≡ 1 ( mod p ) {\displaystyle (ab)^{x}\equiv 1{\pmod {p}}} とすれば、
原始根

( a b ) e x ≡ 1 {\displaystyle (ab)^{ex}\equiv 1} より b e x ≡ ( a e ) x ( b e x ) ≡ ( a b ) e x ≡ 1 ( mod p ) {\displaystyle b^{ex}\equiv (a^{e})^{x}(b^{ex})\equiv (ab)^{ex}\equiv 1{\pmod {p}}} となる。したがって、位数の法則によって f | e x {\displaystyle f\,|\,ex} となる。 ( e , f ) = 1 {\displaystyle (e,f)=1} だから、定理 1.6 によって f | x {\displaystyle f\,|\,x} 同様にして、 ( a b ) x n ≡ 1 {\displaystyle (ab)^{xn}\equiv 1} より、 x {\displaystyle x} は e {\displaystyle e} の倍数、したがって x {\displaystyle x} は m , n {\displaystyle m,n} の公倍数となり、 x = e f {\displaystyle x=ef}
原始根

したがって a b {\displaystyle ab} の位数は e f > e ( ∵ f > 1 ) {\displaystyle ef>e\ (\because f>1)} となり、位数がより大きい数を見つけることが出来た。
原始根

(ii) gcd ( e , f ) = d > 1 {\displaystyle \gcd(e,f)=d>1} のとき
原始根

l c m ( e , f ) = l {\displaystyle {\rm {lcm}}(e,f)=l} とおくと、定理 1.5 より、 d l = e f ⟺ l = e f d = e ′ f ′ {\displaystyle dl=ef\iff l={\frac {ef}{d}}=e'f'} とおいて、 e ′ | e , f ′ | f , ( e ′ , f ′ ) = 1 {\displaystyle e'\,|\,e,f'\,|\,f,(e',f')=1} とすることができる。 (※1)
原始根

a e e ′ , b f f ′ {\displaystyle a^{\frac {e}{e'}},b^{\frac {f}{f'}}} の位数はそれぞれ、定理 2.2.3 より e gcd ( e e ′ , e ) = e ′ , f gcd ( f f ′ , f ) = f ′ {\displaystyle {\frac {e}{\gcd({\frac {e}{e'}},e)}}=e',{\frac {f}{\gcd({\frac {f}{f'}},f)}}=f'} である。(※2)
原始根

したがって、 ( e e ′ , f f ′ ) = 1 {\displaystyle ({\frac {e}{e'}},{\frac {f}{f'}})=1} であることから、(i) より a e e ′ b f f ′ {\displaystyle a^{\frac {e}{e'}}b^{\frac {f}{f'}}} の位数は e ′ f ′ = l = l c m ( e , f ) {\displaystyle e'f'=l={\rm {lcm}}(e,f)} となる。
原始根

先に述べたように e {\displaystyle e} は f {\displaystyle f} の倍数ではないから a b {\displaystyle ab} の位数は l > e {\displaystyle l>e} となり、やはり a {\displaystyle a} の位数より大きい。
原始根

(i), (ii) より、位数が大きい数を生成することが出来た。これを繰り返していけば、アルキメデスの公理から位数が p − 1 {\displaystyle p-1} となる数、すなわち原始根が必ずみつかることが証明され、よって原始根の存在も証明された。
原始根

注釈
原始根

(※1)について :
原始根

それぞれを全ての素数による素因数分解をした形、 e = p 0 a 0 p 1 a 1 ⋯ , f = q 0 b 0 q 1 b 1 ⋯ {\displaystyle e=p_{0}^{a_{0}}p_{1}^{a_{1}}\cdots ,f=q_{0}^{b_{0}}q_{1}{b^{1}}\cdots } を考える。(因数に含まれない素数は指数を 0 にする)
原始根

これらの全ての素因数のうち、指数の大きい方をどちらにあるかにしたがって e ′ , f ′ {\displaystyle e',f'} に分配する。指数が同じならどちらでも構わない。このように分配すれば条件を満たす e ′ , f ′ {\displaystyle e',f'} を構成できる。
原始根

(※2)について :
原始根

e = e ′ E , f = f ′ F {\displaystyle e=e'E,f=f'F} とおくと、 e e ′ = E , f f ′ = F {\displaystyle {\frac {e}{e'}}=E,{\frac {f}{f'}}=F} となり、
原始根

e gcd ( e e ′ , e ) = e gcd ( E , e ′ E ) = e E = e ′ {\displaystyle {\begin{aligned}{\frac {e}{\gcd({\frac {e}{e'}},e)}}&={\frac {e}{\gcd(E,e'E)}}\\&={\frac {e}{E}}\\&=e'\end{aligned}}}
原始根

f gcd ( f f ′ , f ) = f gcd ( F , f ′ F ) = f F = f ′ {\displaystyle {\begin{aligned}{\frac {f}{\gcd({\frac {f}{f'}},f)}}&={\frac {f}{\gcd(F,f'F)}}\\&={\frac {f}{F}}\\&=f'\end{aligned}}}
原始根

( e e ′ , f f ′ ) = ( e ′ , f ′ ) = 1 {\displaystyle ({\frac {e}{e'}},{\frac {f}{f'}})=(e',f')=1}
原始根

例 41 の原始根を求めてみる。
原始根

まずは、2 の位数を求めると、10 であることが計算すれば分かる(このとき位数の法則より、41-1 = 40 の約数のみを調べれば良い)。
原始根

2 2 = 4 , 2 3 = 8 , 2 4 = 16 , 2 5 = 32 , 2 6 ≡ 23 , 2 7 ≡ 5 , 2 8 ≡ 10 , 2 9 ≡ 20 , 2 10 ≡ 40 {\displaystyle 2^{2}=4,2^{3}=8,2^{4}=16,2^{5}=32,2^{6}\equiv 23,2^{7}\equiv 5,2^{8}\equiv 10,2^{9}\equiv 20,2^{10}\equiv 40} となり、3 は右辺に出てこない。3 の位数を求めると、8 であることが分かる。
原始根

ところで、 2 20 5 = 2 4 {\displaystyle 2^{\frac {20}{5}}=2^{4}} の位数は 5 である。 ( 2 4 , 3 ) = 1 {\displaystyle (2^{4},3)=1} なので上記の証明の (i) の場合に対応する。したがって、 2 4 ⋅ 3 = 48 ≡ 7 {\displaystyle 2^{4}\cdot 3=48\equiv 7} の位数は 5 ⋅ 8 = 40 {\displaystyle 5\cdot 8=40} である。すなわち原始根が見つかったのである。
原始根

41 までの素数を法とする原始根は次のとおりである。
原始根

問 43 を法とする原始根を求めよ。
原始根

41 のように、最小原始根が素数ではない場合もある。
原始根

このように、与えられた法に対して原始根が存在することは初等的に示される。しかし、逆に与えられた数を原始根に持つ法が存在するか否かは明らかではない。累乗数が原始根たりえないことは明らかだが、それ以外の数については明らかではない。たとえば、累乗数ではない、どのような数についても、それを原始根に持つ法が無数に存在するか否かは未だに解決されていない。
原始根

素数 p {\displaystyle p} を法としての原始根の1つを r {\displaystyle r} とおく。 { 1 , r , r 2 , ⋯ , r p − 2 } {\displaystyle \{1,r,r^{2},\cdots ,r^{p-2}\}} は剰余系である。また、どれも p {\displaystyle p} と互いに素である(既約剰余系である)。特に a {\displaystyle a} が p {\displaystyle p} と互いに素な数であるとき a ≡ r l ( mod p ) {\displaystyle a\equiv r^{l}{\pmod {p}}} となる整数 l ( 0 ≤ l ≤ p − 2 ) {\displaystyle l(0\leq l\leq p-2)} が1つ定まる。
原始根

原始根の存在証明の中で、すでにどれも互いに不合同であることは証明されている。また法は素数であることから、これらはどれも p {\displaystyle p} と互いに素で、剰余系をなす。
原始根

フェルマーの小定理と併せて、上記の l {\displaystyle l} に対し a ≡ r k ( mod p ) ⟺ k ≡ l ( mod p − 1 ) {\displaystyle a\equiv r^{k}{\pmod {p}}\iff k\equiv l{\pmod {p-1}}} となることがわかる。
原始根

a {\displaystyle a} が p {\displaystyle p} と互いに素な数とする。素数 p {\displaystyle p} を法としての原始根の1つを r {\displaystyle r} とし k {\displaystyle k} を a ≡ r k ( mod p ) {\displaystyle a\equiv r^{k}{\pmod {p}}} となる整数とおくと a ( mod p ) {\displaystyle a{\pmod {p}}} の位数は ( p − 1 ) / gcd ( p − 1 , k ) {\displaystyle (p-1)/\gcd(p-1,k)} に等しい。
原始根

実際このとき定理 1.6' より a e ≡ 1 ( mod p ) ⟺ r k e ≡ 1 ( mod p ) ⟺ ( p − 1 ) | k e ⟺ ( p − 1 ) / gcd ( p − 1 , k ) | e {\displaystyle 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} である。
原始根・指数

定理 2.3.1 で見たように法の素数を p {\displaystyle p} とおき、 r {\displaystyle r} を原始根とすると、任意の n {\displaystyle n} について
原始根・指数

r a ≡ n ( mod p ) {\displaystyle r^{a}\equiv n{\pmod {p}}} となる 0 ≦ a < p − 1 {\displaystyle 0\leqq a<p-1} がただ一つ存在する。この a {\displaystyle a} を 「 r {\displaystyle r} を底とする n {\displaystyle n} の指数 (index)」という。またこれを、次のように表記する。
原始根・指数

I n d r n = a {\displaystyle \mathrm {Ind} _{r}n=a} あるいは l o g r n = a . {\displaystyle \mathrm {log} _{r}n=a.}
原始根・指数

定理 2.3.1 で見たように
原始根・指数

であることがわかる。
原始根・指数

p , r {\displaystyle p,r} をそれぞれ素数とその原始根とすると、
原始根・指数

であることがわかる。
原始根・指数

次に見るように、指数は対数関数と類似した性質を持っている。それで、指数を r {\displaystyle r} を底とする n {\displaystyle n} の離散対数 (discrete logarithm)と呼ぶこともある(古くから指数と呼ばれていたが、近年、暗号系への応用に伴って、離散対数問題として知られるようになった)。
原始根・指数

素数 p {\displaystyle p} に対し a , b {\displaystyle a,b} を p {\displaystyle p} と互いに素な数、 r , r ′ {\displaystyle r,r'} を p {\displaystyle p} を法とする原始根とすると、
原始根・指数

{ I n d r a b ≡ I n d r a + I n d r b , I n d r a n ≡ n I n d r a , I n d r ′ a = I n d r ′ r I n d r a ( mod p − 1 ) . {\displaystyle {\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}}.}
原始根・指数

証明 I n d r a = α , I n d r b = β {\displaystyle \mathrm {Ind} _{r}a=\alpha ,\mathrm {Ind} _{r}b=\beta } とおくと、定義より r α ≡ a , r β ≡ b ( mod p ) {\displaystyle r^{\alpha }\equiv a,r^{\beta }\equiv b{\pmod {p}}} であるから a b ≡ r α + β ( mod p ) {\displaystyle ab\equiv r^{\alpha +\beta }{\pmod {p}}} がすぐに分かる。よって
原始根・指数

ここから I n d r a n ≡ n I n d r a {\displaystyle \mathrm {Ind} _{r}a^{n}\equiv n\mathrm {Ind} _{r}a} は n {\displaystyle n} に関する数学的帰納法で容易に証明される。
原始根・指数

また I n d r a = α , I n d r ′ r = ρ {\displaystyle \mathrm {Ind} _{r}a=\alpha ,\mathrm {Ind} _{r'}r=\rho } とおくと r α ≡ a , r ′ ρ ≡ r ( mod p ) {\displaystyle r^{\alpha }\equiv a,\ r'^{\rho }\equiv r{\pmod {p}}} より r ′ ρ α = ( r ′ ρ ) α ≡ r α ≡ a ( mod p ) {\displaystyle r'^{\rho \alpha }=(r'^{\rho })^{\alpha }\equiv r^{\alpha }\equiv a{\pmod {p}}} なので I n d r ′ a ≡ ρ α ≡ I n d r ′ r I n d r a ( mod p − 1 ) {\displaystyle \mathrm {Ind} _{r'}a\equiv \rho \alpha \equiv \mathrm {Ind} _{r'}r\mathrm {Ind} _{r}a{\pmod {p-1}}} である。
原始根の応用例

p ≠ 2 , r {\displaystyle p\neq 2,r} をそれぞれ素数とその原始根とする。
原始根の応用例

(1) r p − 1 2 ≡ − 1 ( mod p ) {\displaystyle r^{\frac {p-1}{2}}\equiv -1{\pmod {p}}} つまり I n d r ( − 1 ) = p − 1 2 {\displaystyle \mathrm {Ind} _{r}(-1)={\frac {p-1}{2}}} である。
原始根の応用例

証明 ( r p − 1 2 ) 2 ≡ r p − 1 ≡ 1 ( mod p ) {\displaystyle (r^{\frac {p-1}{2}})^{2}\equiv r^{p-1}\equiv 1{\pmod {p}}} であるが x 2 ≡ 1 ( mod p ) {\displaystyle x^{2}\equiv 1{\pmod {p}}} の解は x ≡ ± 1 ( mod p ) {\displaystyle x\equiv \pm 1{\pmod {p}}} だから r p − 1 2 ≡ ± 1 ( mod p ) {\displaystyle r^{\frac {p-1}{2}}\equiv \pm 1{\pmod {p}}} がわかる。しかし r {\displaystyle r} は原始根であるから r p − 1 2 ≢ 1 ( mod p ) {\displaystyle r^{\frac {p-1}{2}}\not \equiv 1{\pmod {p}}} なので r p − 1 2 ≡ − 1 ( mod p ) {\displaystyle r^{\frac {p-1}{2}}\equiv -1{\pmod {p}}} でなければならない。
原始根の応用例

(2) a + b = p {\displaystyle a+b=p} のとき I n d r a − I n d r b ≡ p − 1 2 ( mod p − 1 ) {\displaystyle \mathrm {Ind} _{r}a-\mathrm {Ind} _{r}b\equiv {\frac {p-1}{2}}{\pmod {p-1}}}
原始根の応用例

証明 実際 a ≡ − b ( mod p ) {\displaystyle a\equiv -b{\pmod {p}}} なので
原始根の応用例

である。
原始根の応用例

(3) k {\displaystyle k} が p − 1 {\displaystyle p-1} で割り切れないとき、
原始根の応用例

証明 原始根のべき乗は既約剰余系を成すので、この和は
原始根の応用例

となる。これを r k − 1 {\displaystyle r^{k}-1} 倍すると
原始根の応用例

となるが、 r {\displaystyle r} は p {\displaystyle p} を法とする原始根だから r k ≢ 1 {\displaystyle r^{k}\not \equiv 1} である。したがって、
原始根の応用例

となる。
原始根の応用例

また、原始根をウィルソンの定理の別証明に用いることもできる。
原始根の応用例

ここで (1) より r p − 1 2 ≡ − 1 ( mod p ) {\displaystyle r^{\frac {p-1}{2}}\equiv -1{\pmod {p}}} なので ( p − 1 ) ! ≡ ( − 1 ) p − 2 {\displaystyle (p-1)!\equiv (-1)^{p-2}} となるが、 p {\displaystyle p} は奇素数なので、これは -1 に合同である。 また ( 2 − 1 ) ! = 1 ! = 1 ≡ − 1 ( mod 2 ) {\displaystyle (2-1)!=1!=1\equiv -1{\pmod {2}}} であるから、ウィルソンの定理が証明された。
原始根とべき剰余

x n ≡ a ( mod p ) {\displaystyle x^{n}\equiv a{\pmod {p}}} が解を持つか、持たないかにしたがって a {\displaystyle a} を p {\displaystyle p} の n {\displaystyle n} 次剰余(べき剰余)、非剰余という。 べき剰余について、次の基本的な定理が成り立つ。
原始根とべき剰余

p {\displaystyle p} を素数、 a {\displaystyle a} を p {\displaystyle p} で割り切れない数とする。 n ≠ 0 {\displaystyle n\neq 0} を整数とし e = gcd ( n , p − 1 ) , f = ( p − 1 ) / e {\displaystyle e=\gcd(n,p-1),f=(p-1)/e} とおく。 このとき次の3つはいずれも同値である。
原始根とべき剰余

またこのとき x n ≡ a ( mod p ) {\displaystyle x^{n}\equiv a{\pmod {p}}} の解の1つを x 0 {\displaystyle x_{0}} とすると、この合同方程式の解は
原始根とべき剰余

の e {\displaystyle e} 個である。
原始根とべき剰余

証明 r {\displaystyle r} を原始根とし k = I n d r a {\displaystyle k=\mathrm {Ind} _{r}a} とおく。 t = n / e {\displaystyle t=n/e} とおくと gcd ( t , f ) = 1 {\displaystyle \gcd(t,f)=1} より t u ≡ 1 ( mod f ) {\displaystyle tu\equiv 1{\pmod {f}}} となる整数 u {\displaystyle u} が存在する。 第一に e | k {\displaystyle e|k} ならば x = r k u / e {\displaystyle x=r^{ku/e}} は解である。実際
原始根とべき剰余

となるが ( p − 1 ) | e f | k f | k ( t u − 1 ) {\displaystyle (p-1)|ef|kf|k(tu-1)} より k t u ≡ k ( mod p − 1 ) {\displaystyle ktu\equiv k{\pmod {p-1}}} だから
原始根とべき剰余

第二に x n ≡ a ( mod p ) {\displaystyle x^{n}\equiv a{\pmod {p}}} ならば n f = n ( p − 1 ) / gcd ( n , p − 1 ) = ( p − 1 ) t {\displaystyle nf=n(p-1)/\gcd(n,p-1)=(p-1)t} より a f ≡ x n f ≡ 1 ( mod p ) {\displaystyle a^{f}\equiv x^{nf}\equiv 1{\pmod {p}}} である。
原始根とべき剰余

第三に a f ≡ 1 ( mod p ) {\displaystyle a^{f}\equiv 1{\pmod {p}}} とする。 r {\displaystyle r} を原始根とし k = I n d r a {\displaystyle k=\mathrm {Ind} _{r}a} とおくと r k f ≡ 1 ( mod p ) {\displaystyle r^{kf}\equiv 1{\pmod {p}}} つまり ( p − 1 ) | k f {\displaystyle (p-1)|kf} であるから e = ( p − 1 ) / f | k {\displaystyle e=(p-1)/f|k} である。
原始根とべき剰余

さて x n ≡ a ( mod p ) {\displaystyle x^{n}\equiv a{\pmod {p}}} の解が存在するとして x 0 = r m {\displaystyle x_{0}=r^{m}} を解の1つとする。 このとき 定理 1.6' より
原始根とべき剰余

であるから
原始根とべき剰余

となる。 e f = p − 1 {\displaystyle ef=p-1} より解は x 0 r f l , l = 0 , 1 , ... e − 1 {\displaystyle x_{0}r^{fl},l=0,1,\ldots e-1} の e {\displaystyle e} 個である。
原始根とべき剰余

このことから、 e = gcd ( n , p − 1 ) {\displaystyle e=\gcd(n,p-1)} とおくと x n ≡ a ( mod p ) {\displaystyle x^{n}\equiv a{\pmod {p}}} が解を持つことと x e ≡ a ( mod p ) {\displaystyle x^{e}\equiv a{\pmod {p}}} が解を持つことは同値であることがすぐにわかる。 よって、べき剰余を考える上では、 n {\displaystyle n} が p − 1 {\displaystyle p-1} の約数のときが本質的であると言える。
原始根とべき剰余

n > 1 {\displaystyle n>1} が p − 1 {\displaystyle p-1} の約数のとき n {\displaystyle n} 次剰余は原始根ではない。なぜなら a ( p − 1 ) / n ≡ 1 ( mod p ) {\displaystyle a^{(p-1)/n}\equiv 1{\pmod {p}}} より a {\displaystyle a} の位数は p − 1 {\displaystyle p-1} より小さくなるからである。
原始根とべき剰余

べき剰余については、後に初等整数論/べき剰余で詳しく考察する。