以下の内容はhttps://put3y19ea1n0r9er.hatenablog.com/entry/2019/03/08/183820より取得しました。

循環数列

数列

循環数列についての問題です．解答は下部に載せました．

問題

{ \displaystyle i } を虚数単位，{ \displaystyle n } および { \displaystyle m } を自然数，{ \displaystyle z } を整数とする．このとき，次の問いに答えよ．

１．

{ \displaystyle \sum^{m}_{l=1} \exp \left( \frac{2 \pi i}{m} l \right) =0 }

が成り立つことを証明せよ．

２．

{ \displaystyle z } が { \displaystyle m } の倍数であるとき，

{ \displaystyle \sum^{m}_{l=1} \exp \left( \frac{2 \pi i}{m} l z \right) =m }

であることを証明せよ．

３．

{ \displaystyle z } が { \displaystyle m } の倍数でないとき，

{ \displaystyle \sum^{m}_{l=1} \exp \left( \frac{2 \pi i}{m} l z \right) =0 }

であることを証明せよ．

４．

{ \displaystyle a_1 \ , \ a_2 \ , \ \ldots \ , \ a_m \ , \ a_1 \ , \ a_2 \ , \ \ldots \ ,\ a_m \ , \ a_1 \ , \ \ldots }

というように，{ \displaystyle m } 個おきに同じ項が繰り返される数列を周期 { \displaystyle m } の循環数列と呼ぶ．この数列の一般項 { \displaystyle a_n } を求めよ．

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

解答

１．

正 { \displaystyle m } 角形の底辺の右隣の辺を { \displaystyle 1 } 番目として，そこから反時計回りに各辺に番号をつける．各辺を終点から始点の向きが反時計回りであるベクトルとみなすと，{ \displaystyle l } 番目の辺は複素平面において { \displaystyle \exp \left( \frac{2 \pi i}{m} l \right) } で表されるベクトルと等しい．よって，{ \displaystyle \sum^{m}_{l=1} \exp \left( \frac{2 \pi i}{m} l \right) } は正 { \displaystyle m } 角形の底辺の右側の頂点から反時計回りに一周して同じ点に戻ることを表している．ゆえに，

{ \displaystyle \sum^{m}_{l=1} \exp \left( \frac{2 \pi i}{m} l \right) =0 }

は成り立つ．

 

２．

{ \displaystyle z } は { \displaystyle m } の倍数であるから，{ \displaystyle z = mq }（{ \displaystyle q } は整数）とおくと，

     { \displaystyle \sum^{m}_{l=1} \exp \left( \frac{2 \pi i}{m} l z \right)  }

{ \displaystyle = \sum^{m}_{l=1} \exp \left( \frac{2 \pi i}{m} l mq \right) }

{ \displaystyle = \sum^{m}_{l=1} \exp \left( {2 \pi i} l q \right) }

{ \displaystyle = \sum^{m}_{l=1} 1 }

{ \displaystyle = m }

 

３．

 { \displaystyle z } は { \displaystyle m } の倍数でないから，次のように場合分けをする．

[１] { \displaystyle z } と { \displaystyle m } が互いに素である場合

まず，次の定理を証明する．

 

定理１：{ \displaystyle l_1 } および { \displaystyle l_2 } を，{ \displaystyle 1 \leq l_1 \leq m } ，{ \displaystyle 1 \leq l_2 \leq m } ，{ \displaystyle  l_1 \neq l_2 } を満たす自然数とする．このとき，{ \displaystyle l_1 z \bmod m \neq l_2 z \bmod m } が成り立つ．

証明：{ \displaystyle l_1 z \bmod m = l_2 z \bmod m } と仮定すると，次式が成り立つ．

{ \displaystyle l_1 z =a m + c \ \ldots (1) }

{ \displaystyle l_2 z =b m + c \ \ldots (2) }

ここで，{ \displaystyle a } と { \displaystyle b } は互いに相異なる整数であり，{ \displaystyle c } は { \displaystyle 1 \leq c \leq m } を満たす自然数である．

{ \displaystyle (1) - (2) } より，次式が成り立つ．

{ \displaystyle (l_1 - l_2) z = (a - b ) m}

ここで，{ \displaystyle 1 \leq l_1 \leq m } ，{ \displaystyle 1 \leq l_2 \leq m } より，{ \displaystyle 1 \leq l_1 - l_2 \leq m-1 } であるから，{ \displaystyle l_1 - l_2 } は { \displaystyle m } の倍数ではない．よって，{ \displaystyle z } は { \displaystyle m } と { \displaystyle 1 } 以外の公約数を持つことになるが，これは { \displaystyle z } と { \displaystyle m } が互いに素であることと矛盾する．

よって，{ \displaystyle l_1 z\bmod m \neq l_2  z \bmod m } は成り立つ．

 

定理１と，{ \displaystyle \exp \left( \frac{2 \pi i}{m} l \right) =  \exp \left( \frac{2 \pi i}{m} (m+l) \right) } から，{ \displaystyle \sum^{m}_{l=1} \exp \left( \frac{2 \pi i}{m} l z \right) } は正 { \displaystyle m } 角形の各辺を表すベクトルをすべて足し合わせたものに等しいといえる．

よって，次式が成り立つ．

{ \displaystyle \sum^{m}_{l=1} \exp \left( \frac{2 \pi i}{m} l z \right) = \sum^{m}_{l=1} \exp \left( \frac{2 \pi i}{m} l \right) =0 }

 

[２] { \displaystyle z } と { \displaystyle m } が最大公約数 { \displaystyle q \ (q \neq 1 \ , \ q \neq m )} を持つ場合

まず，次の定理を証明する．

 

定理２：{ \displaystyle s } ，{ \displaystyle t } および { \displaystyle u } を整数とする．このとき，次が成立する．

{ \displaystyle u \cdot (s \bmod t ) = su \bmod tu }

{ \displaystyle \frac{1}{t} \cdot (s \bmod t ) = \frac{1}{tu} \cdot (su \bmod tu) }

証明：{ \displaystyle s=tv+w \ (v } は整数，{ \displaystyle w } は { \displaystyle 1 \leq w \leq t-1 } を満たす自然数 { \displaystyle ) } とおく．このとき，{ \displaystyle su=tuv+uw } である．すると，

{ \displaystyle s \bmod t = w }

{ \displaystyle su \bmod tu = uw = u \cdot (s \bmod t ) }

となる．また，次も成り立つ．

{ \displaystyle \frac{1}{t} \cdot (s \bmod t ) = \frac{1}{tu} \cdot (su \bmod tu) = \frac{w}{t} }

 

続いて，次の定理を証明する．

 

定理３： { \displaystyle s } を整数とする．このとき，次式が成り立つ．

{ \displaystyle zs \bmod m = z \left(s+ \frac{m}{q} \right) \bmod m }

証明：{ \displaystyle z= t_1 q } ，{ \displaystyle  m= t_2 q} とおく．ここで，{ \displaystyle t_1 } は整数，{ \displaystyle t_2 } は自然数であり，{ \displaystyle t_1 } と { \displaystyle t_2 } は互いに素である．このとき，

     { \displaystyle zs \bmod m }

{ \displaystyle = t_1 qs \bmod t_2 q }

 

     { \displaystyle z \left(s+ \frac{m}{q} \right) \bmod m }

{ \displaystyle = t_1 q \left(s+ t_2 \right) \bmod t_2 q }

{ \displaystyle = \left( t_1 qs + t_1 t_2 q \right) \bmod t_2 q }

{ \displaystyle = t_1 qs \bmod t_2 q }

{ \displaystyle = zs \bmod m }

 

定理１，定理２，定理３と { \displaystyle \exp \left( \frac{2 \pi i}{m} l \right) =  \exp \left( \frac{2 \pi i}{m} (m+l) \right) } から，{ \displaystyle \sum^{m}_{l=1} \exp \left( \frac{2 \pi i}{m} l z \right) } は正 { \displaystyle \frac{m}{q} } 角形の各辺を表すベクトルをすべて足し合わせて { \displaystyle q } 倍したものに等しいといえる．よって，

     { \displaystyle \sum^{m}_{l=1} \exp \left( \frac{2 \pi i}{m} l z \right) }

{ \displaystyle = q \sum^{ \frac{m}{q} }_{l=1} \exp \left( \frac{2 \pi i}{m} l \right) }

{ \displaystyle = q \cdot 0 }

{ \displaystyle = 0 }

 

[１]，[２]より，{ \displaystyle z } が { \displaystyle m } の倍数でないとき，

{ \displaystyle \sum^{m}_{l=1} \exp \left( \frac{2 \pi i}{m} l z \right) =0 }

 

４．

周期 { \displaystyle m } の循環数列は { \displaystyle n \bmod m = k } とすると，第 { \displaystyle n } 項は { \displaystyle a_k } となる．そのため，次式は周期 { \displaystyle m } の循環数列の一般項 { \displaystyle a_n } となる．

{ \displaystyle a_n = \frac{1}{m} \sum^{m}_{k=1} a_k \sum^{m}_{l=1} \exp \left( \frac{2 \pi i}{m} l (n-k) \right) }

 

 

 


以上の内容はhttps://put3y19ea1n0r9er.hatenablog.com/entry/2019/03/08/183820より取得しました。
このページはhttp://font.textar.tv/のウェブフォントを使用してます
不具合報告/要望等はこちらへお願いします。
モバイルやる夫Viewer Ver0.14