線形合同式と数列周期

質問

a,b,kを a≡1(mod4)、bと2との最大公約数が1、k>=2 を満たす自然数とすると、
線形合同式　x_(n+1)≡a*(x_n)+b mod 2^k ただし 0<= (x_n) <2^k
で定義される0から(2^k)-1の間の整数による数列{x_n} は、任意の初期値x_0 に対して
周期が2^kであることを示せ。

わかりません。。よろしくお願いします！！

回答No.1

ramayana · ベストアンサー

（準備１：　aについて）

a=1のときは簡単なので、a≠1の前提で説明します。a = 4m + 1とすると、次が成立します（m≠0）。

　　[1] a^(2^k) = 1 mod 2^(k+ 2)・m　（kに関する数学的帰納法で分かる）

　　[2] (a^(n-1) + a^(n-2) + ・・・ +1)(a-1) = a^n - 1　（あたりまえ）

　　[3] 　a^(2^k-1) + a^(2^k-2) + ・・・ + 1 = 0 mod 2^k　（[1]と[2]から）

　　[4] 2^(k-1)≦n< 2^kのとき、n' = n- 2^(k-1)として、
　　　　　　a^n+ ・・・ + 1 = a^(2^(k-1)) (a^n'+a^( n'-1)+・・・+1) + a^(2^(k-1)-1) + ・・・ + 1
　　　　　　　　　　　　　　　　（あたりまえ）

　　[5] n < 2^kのとき、a^n+ ・・・ + 1 ≠ 0 mod 2^k
　　　　　　　　　（[1]、[3]、[4]を使い、kに関する数学的帰納法で分かる）

　　[6] n' < n < 2^kのとき、
　　　　　　　　(a^n+ ・・・ + 1) - (a^n'+ ・・・ + 1) = a^(n'+1) (a^(n-n'-1)+ ・・・ +1)
　　　　　　　　　　　　　（あたりまえ）

　　[7] n' < n < 2^kのとき、
　　　　　　　　a^n'+ ・・・ + 1 ≠ a^n+ ・・・ + 1 mod 2^k　（[5]、[6]から）

（準備２：　x_nについて）

漸化式を繰り返し適用して、次が成立します。

　　　　x_n = a^n・x_0 + b・(a^(n-1) + ・・・ +1)

（x_0 = 0のとき）

x_0 = 0のときは、x_n = b・(a^(n-1) + ・・・ +1)です。bが奇数であることを考慮し、[7]により、

　　[8] x_0 = 0のとき、x_0、x_1、・・・、x_(2^k-1)がすべて異なる

となります。よって、[3]も考慮して、数列｛x_n mod 2^k｝が周期2^kで巡回することが分かります。

（x_0が任意のとき）

「0を初期値とし、同じ漸化式をみたす数列」を{y_n}とします。[8]により、適当なrがあって、x_0は、y_rとmod 2^kで一致します。その後の値は、x_n = y_(n+r) mod 2^kとなります。したがって、x_0が任意の場合も、数列｛x_n mod 2^k｝は、周期2^kで巡回します。