線形合同法（擬似乱数生成法）の周期 - tsujimotterのノートブック

世の中の現象の中には「ランダム」な現象が多々あります。たとえば、サイコロを振るのは分かりやすいランダムな現象の例です。他にも天気や地震、ギャンブルなども分かりやすいランダムな現象の例です。

一方で、コンピュータの中で行われる計算は、一定のアルゴリズムにより定められた計算が順次実行されることになるため、原理的にはランダムになることはありません。

このことはコンピュータ内でランダムな現象をシミュレーションするにあたって問題になります。そこで「決められた手順によって生成されるランダムっぽく振る舞う数列」をいかにして作るかが重要になるわけですね。このような数列を擬似乱数と言います。

コンピュータによって擬似乱数を生成する手法は、これまでもさまざまな手法が提案されています。今回は、その中でも特に有名な手法である線形合同法について考えたいと思います。

最近はもっと良い疑似乱数の生成法が発見されているので、線形合同法はあまり使われていないと聞きます。しかし、一昔前のC言語等の乱数生成には、この方法が普通に使われていました。

簡単に線形合同法について説明しましょう。線形合同法とは次のようなアルゴリズムです。

整数の3つ組 $(a, b, M)$ を考えます。とくに、 $a > 0, \; b \geq 0, \; M > 0$ とし、 $a < M, \; b < M$ としておきます。

$x_0$ を $0 \leq x_0 \leq M-1$ であるような整数とし、整数 $x_1, x_2, x_3, \ldots$ を次の漸化式によって定めます：

$x_{n+1} \equiv a x_n + b \pmod{M} \tag{1}$

ただし、 $x_n$ は $\{0, 1, 2, \ldots, M-1\}$ の中からとることにします。

このように数列 $\{x_n\}$ を選ぶと、 $x_0$ を決める毎に異なる疑似乱数の列が得られるというわけです。

たとえば、 $a = 13, b = 5, M = 24$ とします。このとき、 $x_0 = 8$ とすると

$\begin{align*} x_0 &= 8, \\ x_1 &= 13\times 8 + 5 = 109 \equiv 13 \pmod{24}, \\ x_2 &= 13\times 13 + 5 = 174 \equiv 6 \pmod{24}, \\ x_3 &= 13\times 6 + 5 = 83 \equiv 11 \pmod{24}, \\ & \vdots \end{align*}$

のように数列 $8, 13, 6, 11, \ldots$ が得られます。

今回の数列は結構優秀で、数列をこのまま続けていくと、こうなるのですが・・・

${\bf 8},13,6,11,4,9,2,7,0,5,22,3,20,1,18,23,16,21,14,19,12,17,10,15,{\bf 8}\ldots$

実は、 $8$ からスタートして $8$ に戻ってくるまで、 $0$ から $23$ までの数がすべて１回ずつ出力されています。つまり、この数列の周期は $24$ というわけですね。周期は法 $M$ を超えることはないので、これが最大周期になります。

パラメータ $(a, b, M)$ によっては最大周期とならないケースも存在します。たとえば、 $a = 15, b = 5, M = 24$ とすると

$8,21,11,15,23,15,23,15,23, \ldots$

となりますが、これは $15, 23$ が繰り返されるので、周期 $2$ となります。

あとで述べるように、一般に線形合同法によって得られる数列は周期 $\lambda$ を持ち、その周期は $\lambda \leq M$ となります。

今回のメインテーマは、パラメータ $(a, b, M)$ がどのような条件のとき周期最大（ $\lambda = M$ ）となるのか、という問題です。周期は長ければ長いほど疑似乱数としては優秀だと考えられるので、気になる問題設定です。

線形合同法において最大周期になる必要十分条件は知られていて、以下の定理1が成り立ちます。

定理1

パラメータ $(a, b, M)$ に対する周期を $\lambda$ とする。このとき、次の必要十分条件が成り立つ：

$\newcommand{\HLNO}{\unicode[\sans-serif,STIXGeneral]{x306E}} \lambda = M \;\; \Longleftrightarrow \;\; \begin{cases} \text{(i)}\;\;\; (b, M) = 1 \\ \text{(ii)} \;\;\; \text{任意}\HLNO{奇素数} \; p \; \text{に対して} \;\; p\mid M \; \Longrightarrow \; p \mid (a-1) \\ \text{(iii)} \;\;\; 4\mid M \; \Longrightarrow \; 4 \mid (a-1) \\ \end{cases}$

実際、 $a = 13, \; b = 5, \; M = 24$ のケースでは、条件 (i), (ii), (iii) を満たすので最大周期 $\lambda = 24$ になったというわけですね。

しかし、一体どうしてこのような必要十分条件になるのか気になりますね。そこで、今回の記事は定理1を証明してみたいと思います。

自力で考えてみてもなかなか難しかったので、証明がどこかに載っていないか調べてみましたが、ネット上で一般的なケースについての証明は見かけませんでした。

その後、Knuth先生の "The Art of Computer Programming Volume2 Seminumerical Algorithms" に証明が載っていることを知り、今回参考にさせていただきました。

The Art of Computer Programming　Volume 2 Seminumerical Algorithms Third Edition 日本語版 (アスキードワンゴ)

作者:Donald E. Knuth,斎藤博昭,長尾高弘,松井祥悟,松井孝雄,山内斉
ドワンゴ

Amazon

しかしながら、証明を読んでいて納得いかない部分がいくつかありました。

こちらの記事では、大枠の証明は上記に従いつつも、いくらか自分流に修正したものをまとめたいと思います。

周期を持つことの確認

そもそも線形合同法が一般に周期を持つことについて考えてみましょう。

線形合同法は

$f(x) = ax + b \tag{2}$

という写像を考えて

$x_0, \; x_1 \equiv f(x_0), \; x_2 \equiv f^2(x_0), \; x_3 \equiv f^3(x_0), \; \ldots$

という反復合成によって数列 $x_0, x_1, x_2, x_3, \ldots$ を得る手法でした。

ここで、 $x_n \in \{0, 1, 2, \ldots, M-1\}$ は有限個の集合の元なので、鳩の巣原理によって $x_i = x_j$ となるような非負整数 $i < j$ が存在することになります。

したがって、以降

$x_i = x_j = x_{2(j-i)+i} = x_{3(j-i)+i} = x_{4(j-i)+i} = \cdots$

となり、循環します。

$x_i, x_{i+1}, x_{i+2}, \ldots, x_{j-1}$

を循環節、 $n = j-i$ を循環節の長さと呼ぶことにします。最小の循環節の長さを周期といい $\lambda$ で表すことにします。

以上の議論によって、周期 $\lambda$ を持つことが言えたというわけです。
（一般に、有限集合 $R$ に対して、写像 $f\colon R \to R$ の反復合成によって得られる数列は周期を持ちます。）

また、 $x_i$ から始まる長さ $n$ の循環節があったとすると、 $\lambda \mid n$ であることも次のようにして分かります。

$\lambda \not\mid n, \;\; \lambda < n$ と仮定して、 $n$ を $\lambda$ で割ったあまりを $r$ とします。このとき、　 $\lambda \not\mid n$ より $0 < r < \lambda$ となります。

$x_i$ から長さ $n$ で循環すると

$x_{i+n} = x_i$

となるはずです。

$\lambda$ は周期なので、 $x_{i+n}$ のインデックスから $\lambda$ を引いていっても等号が成り立つはずなので

$x_{i+n} = x_{i+n-\lambda} = x_{i+n-2\lambda} = \cdots = x_{i+r}$

が成り立ちます。しかし、 $x_i = x_{i+r}$ かつ $0 < r < \lambda$ であることは、 $\lambda$ の最小性に反します。したがって、 $\lambda \not\mid n$ は誤りであることがわかり、 $\lambda \mid n$ であることが示されました。　

合成とアフィン変換

$f$ の $n$ 回の合成

$x_n = f^n(x_0) \tag{3}$

の結果を具体的に計算してみましょう。

$n = 1$ のとき：

$x_1 \equiv f(x_0) \equiv ax_0 + b \pmod{M}$

$n = 2$ のとき：

$\begin{align*} x_2 \equiv f(x_1) &\equiv a(ax_0+b) + b \\ &\equiv a^2 x_0 + b(1+a) \pmod{M} \end{align*}$

$n = 3$ のとき：

$\begin{align*} x_3 \equiv f(x_2) &\equiv a(a^2x_0+b(1+a)) + b \\ &\equiv a^3 x_0 + b(1+a+a^2) \pmod{M} \end{align*}$

以上から、一般の $n$ に対して

$\begin{align*} x_n \equiv a^n x_0 + b(1+a+ \cdots + a^{n-1}) \pmod{M} \end{align*} \tag{4}$

が成り立ちます。

実際、 $n - 1$ まで成立すると仮定すると

$\begin{align*} x_n \equiv f(x_{n-1}) &\equiv a(a^{n-1} x_0 + b(1+a+ \cdots + a^{n-2}) ) + b \\ &\equiv a^{n} x_0 + b(1+a+ \cdots + a^{n-1}) \pmod{M} \end{align*}$

となるので、数学的帰納法により式 $(4)$ が示されました。

そんなわけで、 $x_n$ の具体的な行き先がわかりましたので、これを使って周期 $\lambda$ を議論すれば良いわけですね。

最大周期 $\lambda = M$ であることの必要十分条件は、集合としての等号

$\{x_0, x_1, \ldots, x_{M-1}\} = \{ 0, 1, \ldots, M-1\}$

が成立することです。この場合は

$x_n \equiv x_0 \pmod{M}$

となるような最小の $n$ が $M$ に一致するわけです。

また、 $x_0 = 0$ としても一般性は失わないので

$x_n = f^n(0) = b(1+a+ \cdots + a^{n-1}) \equiv 0 \pmod{M}$

となるような最小の $n$ が $M$ であるようなとき、 $\lambda$ が最大周期であるというわけです。

まとめると

$\lambda = M \;\; \Longleftrightarrow \;\; b(1+a+ \cdots + a^{n-1}) \equiv 0 \pmod{M}\;\; \text{なる最小}\HLNO \;n>0\;\text{が}\; M$

ということです。

ところで、今回の

$f(x) = ax + b$

という写像は、 $R = \mathbb{Z}/M\mathbb{Z}$ から $R$ 自身へのアフィン変換となっています。

以前、 $M = p$ が素数のときのアフィン変換の性質について考えたことがありましたが、これの一般化を考えているわけです：
tsujimotter.hatenablog.com

実際、 $a \in R^\times, \; b \in R$ としたアフィン変換全体は群をなし、その構造は半直積

$R^\times \ltimes R$

の構造を持ちます。先ほどの $n$ 回の合成

$f^n(x) = a^n x + b(1+a+ \cdots +a^{n-1})$

も、半直積の群では

$(a, b)^n = (a^n, \; b(1+a+ \cdots +a^{n-1}) )$

に対応します。

したがって、今回の問題は半直積の群における位数 $M$ の元 $(a, b)$ を考えていると読み替えることができそうです。

今回は純粋に初等整数論として取り扱うのでこの視点は用いないのですが、群論的に考えてみても面白いかもしれませんね。

$M = p^e$ に帰着

それでは、今回証明したい定理を改めて確認しましょう。

定理1（再掲）

パラメータ $(a, b, M)$ に対する周期を $\lambda$ とする。このとき、次の必要十分条件が成り立つ：

$\lambda = M \;\; \Longleftrightarrow \;\; \begin{cases} \text{(i)}\;\;\; (b, M) = 1 \\ \text{(ii)} \;\;\; \text{任意}\HLNO{奇素数} \; p \; \text{に対して} \;\; p\mid M \; \Longrightarrow \; p \mid (a-1) \\ \text{(iii)} \;\;\; 4\mid M \; \Longrightarrow \; 4 \mid (a-1) \\ \end{cases}$

定理の条件 (ii), (iii) を見ると、 $M$ の素因数 $p$ に関する条件になっています。そこで、 $M$ の素因数分解をしたくなります。

$M = p_1^{e_1} p_2^{e_2} \cdots p_t^{e_t} \tag{5}$

各素因子のべき $p_j^{e_j}$ について、 $\bmod{p_j^{e_j}}$ を考えます。すなわち、パラメータを $\bmod{p_j^{e_j}}$

$\begin{cases} a_j \equiv a \pmod{p_j^{e_j}} \\ b_j \equiv b \pmod{p_j^{e_j}} \\ M_j = p_j^{e_j} \end{cases}$

としたときの $(a_j, b_j, M_j)$ について、線形合同法の周期を $\lambda_j$ としましょう。

このとき、元々の周期 $\lambda$ は、 $\lambda_1, \lambda_2, \ldots, \lambda_t$ の最小公倍数となっているというのが次の補題1です。

補題1

$M = p_1^{e_1} p_2^{e_2} \cdots p_t^{e_t}$ とし、そのときの線形合同法の周期を $\lambda$ とする。 $\bmod{p_j^{e_j}}$ における周期を上記の通り $\lambda_j$ （ $1\leq j \leq t$ ）とするとき、 $\lambda = \operatorname{LCM}(\lambda_1, \lambda_2, \ldots, \lambda_t)$ となる。

（補題1の証明）互いに素な整数 $m_1, m_2$ 、 $M = m_1 m_2$ について、対応する周期を $\lambda_1, \lambda_2$ としたとき、 $\lambda = \operatorname{LCM}(\lambda_1, \lambda_2)$ であることを示せばよい。

循環節の始まりを $x_0$ としても一般性は失わない。 $x_n = f^n(x_0)$ とする。ここで、 $\lambda$ は周期より

$x_{\lambda} \equiv x_0 \pmod{M}$

であるが、これを $\bmod{m_1}$ すると

$x_{\lambda} \equiv x_0 \pmod{m_1}$

である。したがって、 $x_0, x_1, \ldots, x_{\lambda-1}$ は $\bmod{m_1}$ における長さ $\lambda$ の循環節である。

また、 $\bmod{m_1}$ における周期は $\lambda_1$ なので、 $\lambda_1 \mid \lambda$ が言える。

同じ議論を $\bmod{m_2}$ に対しても行うと、 $\lambda_2 \mid \lambda$ を得る。

したがって、 $\lambda$ は $\lambda_1, \lambda_2$ の公約数である。

一方、一般に $n$ が $\lambda_1, \lambda_2$ の公倍数であれば、 $x_0, x_1, \ldots, x_{n-1}$ は $\bmod{m_1}, \bmod{m_2}$ の循環節になるので

$x_n \equiv x_0 \pmod{m_1}, \;\; x_n \equiv x_0 \pmod{m_2}$

である。中国剰余定理より

$x_n \equiv x_0 \pmod{M}$

が言えるので

$n \; \text{が}\; \lambda_1, \lambda_2 \; \HLNO \text{公倍数} \;\; \Longrightarrow \;\; \lambda\mid n$

が成り立つ。これは $\lambda$ が $\lambda_1, \lambda_2$ の最小公倍数であることを意味する。

（補題1の証明終わり）

鳩の巣原理により $\lambda_j \leq p_j^{e_j}$ であることを使うと、 $\lambda = M$ であることの必要十分条件は次のように得られます：

$\begin{align*} &\lambda = M \\ & \Longleftrightarrow \;\; p_1^{e_1}p_2^{e_2}\cdots p_t^{e_t} = M = \lambda = \operatorname{LCM}(\lambda_1, \lambda_2, \ldots, \lambda_t) \leq \lambda_1 \lambda_2 \cdots \lambda_t \leq p_1^{e_1}p_2^{e_2}\cdots p_t^{e_t} \\ &\Longleftrightarrow \;\; 1\leq j \leq t \; \text{に対して} \; \lambda_j = p_j^{e_j} \end{align*}$

したがって

$\lambda = M \;\; \Longleftrightarrow \;\; 1\leq j \leq t \; \text{に対して} \; \lambda_j = p_j^{e_j} \tag{6}$

が示されました。

よって、 $M = p_j^{e_j}$ のケースに問題は帰着されました。

指数持ち上げ補題

さて、早速 $M = p_j^{e_j}$ のケースについての証明に行きたいところですが、その証明を行うために必要な補題を一つ準備しておきます。これは「指数持ち上げ補題（LTEの補題）」と呼ばれる補題の特別なケースです。

補題2（指数持ち上げ補題）

$p$ を素数とし、

$q = \begin{cases} p & (p \neq 2\;\HLNO\text{とき}) \\ 4 & (p = 2\;\HLNO\text{とき})\end{cases}$

とする。

このとき、 $p$ で割り切れない整数 $x, y$ に対して次が成り立つ：

$x\equiv y \pmod{q} \;\; \Longrightarrow \;\; \operatorname{ord}_p(x^p - y^p) = \operatorname{ord}_p(x - y) + 1$

ここで、 $z \in \mathbb{Q}^\times$ は、整数 $e$ と $(m, p) = 1, \;\; (n, p) = 1, \;\; (m, n) = 1$ なる整数 $m, n$ を用いて

$\displaystyle z = \frac{m}{n}p^e \tag{7}$

と一意的に表せますが、この $e$ によって $\operatorname{ord}_p(z) = e$ と定義されます。これを $z$ の $p$ 進付値 といいます。

（補題2の証明）
$x^p - y^p$ を因数分解すると

$(x^p - y^p) = (x-y)(x^{p-1}+x^{p-2}y+ \cdots + xy^{p-2} + y^{p-1})$

となる。p進付値の加法性により

$\operatorname{ord}_p(x^p - y^p) = \operatorname{ord}_p(x-y) + \operatorname{ord}_p(x^{p-1}+x^{p-2}y+ \cdots + xy^{p-2} + y^{p-1})$

となるので

$\operatorname{ord}_p(x^{p-1}+x^{p-2}y+ \cdots + xy^{p-2} + y^{p-1}) = 1$

が言えれば良い。

ここで左辺を $y^{p-1}$ で割っても $p\not\mid y$ より $p$ 進付値は変わらないので

$\operatorname{ord}_p((x/y)^{p-1}+(x/y)^{p-2}+ \cdots + (x/y) + 1) = 1$

と同値である。

$x/y \equiv 1 \pmod{q}$ なので、 $a \equiv 1 \pmod{q}$ なる整数 $a$ について

$\operatorname{ord}_p(a^{p-1}+a^{p-2}+ \cdots + a + 1) = 1$

が言えれば良い。

$p = 2$ のとき：

$a \equiv 1 \pmod{4}$ より

$a+1 \equiv 1 + 1 \equiv 2 \pmod{4}$

となります。したがって $\operatorname{ord}_p(a+1) = 1$ であり、成立。

$p \neq 2$ のとき：

$a \equiv 1 \pmod{p}$ より、 $a = 1 + pt$ （ $t \in \mathbb{Z}$ ）として

$\begin{align*} a^{p-1} + a^{p-2} + \cdots + a + 1 &= (1+pt)^{p-1} + (1+pt)^{p-2} + \cdots + (1+pt) + 1 \\ &\equiv p + \left\{ (p-1) + (p-2) + \cdots + 1 \right\} pt \pmod{p^2} \\ &\equiv p + \frac{(p-1)t}{2} p^2 \pmod{p^2} \\ &\equiv p \pmod{p^2} \end{align*}$

よって、 $\operatorname{ord}_p( a^{p-1} + a^{p-2} + \cdots + a + 1 ) = 1$ であることが分かる。

以上により

$\operatorname{ord}_p(x^p - y^p) = \operatorname{ord}_p(x - y) + 1$

が示された。

（補題2の証明終わり）

今回は使いませんが、より一般の場合は

$x\equiv y \pmod{q} \;\; \Longrightarrow \;\; \operatorname{ord}_p(x^n - y^n) = \operatorname{ord}_p(x - y) + \operatorname{ord}_p(n)$

という主張になります。詳しくは以下の記事をご覧ください。
integers.hatenablog.com

$M = p^e$ のケースの証明

そんなわけで、 $M = p^e$ における定理を証明するための準備は整いました。示すべき主張は次の通りです。

$M = p^e$ における定理1の主張

$p$ を素数とし、

$q = \begin{cases} p & (p \neq 2\;\HLNO\text{とき}) \\ 4 & (p = 2\;\HLNO\text{とき})\end{cases}$

とする。また、パラメータ $(a, b, p^e)$ における線形合同法の周期を $\lambda$ とする。

このとき、次の必要十分条件が成り立つ：

$\lambda = p^e \;\; \Longleftrightarrow \;\; \begin{cases} \text{(i)}\;\;\; (b, p^e) = 1 \\ \text{(ii)} \;\;\; q \mid (a-1) \end{cases}$

$a = 1$ のケースが特殊なので、そこだけ先に議論しておきましょう。（ここの部分だけは一般の $M$ について議論できます。）

$a = 1$ のとき、 $f(x) = x + b$ となりますが、これは $b$ という数を足し続けることに他なりません。すなわち、 $\mathbb{Z}/M\mathbb{Z}$ において、 $b$ が生成元である条件を考えていることになりますので、次が成り立ちます：

$\lambda = M \;\; \Longleftrightarrow \;\;(b, M) = 1$

つまり、 $a = 1$ における定理が示されました。

よって、以降は $a > 1$ として考えます。このとき、等比数列の和公式により

$\displaystyle 1 + a + \cdots + a^{n-1} = \frac{a^n-1}{a-1} \tag{8}$

であることに注意しましょう。

これを使うと、 $\lambda = p^e$ であることの必要十分条件は

$\begin{align*} \lambda = p^e \;\; &\Longleftrightarrow \;\; b(1+a+ \cdots +a^{n-1}) \equiv 0 \pmod{p^e} \;\; \text{なる最小}\HLNO \; n \; \text{が} \; p^e \;\text{である} \\ &\Longleftrightarrow \;\; b\frac{a^n-1}{a-1} \equiv 0 \pmod{p^e} \;\; \text{なる最小}\HLNO \; n \; \text{が} \; p^e \;\text{である} \end{align*}$

であることに注意しましょう。

$\Longrightarrow$ の証明：

$\lambda = p^e$ とする。すなわち、 $b\frac{a^n-1}{a-1} \equiv 0 \pmod{p^e}$ なる最小の $n$ が $p^e$ であるとします。

$(b, p^e) = 1$ を示す

もし $(b, p^e) \neq 1$ であれば $p\mid b$ であり、 $b$ は $\bmod{p^e}$ の可逆元ではありません。

このとき、 $x_n \neq b\frac{a^n-1}{a-1} \pmod{p^e}$ は $1$ にはならないので、 $\lambda = p^e$ に矛盾します。

ゆえに $(b, p^e) = 1$

$q \mid (a-1)$ を示す

(i) $p$ が奇数のとき：
$p \not\mid (a-1)$ であると仮定します。このとき、 $(a-1)$ は $\bmod{p^e}$ の可逆元であり

$\displaystyle \frac{a^n-1}{a-1} \equiv 0 \pmod{p^e} \;\; \Longleftrightarrow \;\; a^n - 1 \equiv 0\pmod{p^e} \tag{9}$

が成り立ちます。

周期 $\lambda = p^e$ であるので、必要十分条件 $(9)$ と $p\not\mid b$ を使うと

$a^{p^e} - 1 \equiv 0\pmod{p^e}$

となり、 $a^{p^e} \equiv 1\pmod{p^e}$ である。これを $\bmod{p}$ とると

$a^{p^e} \equiv 1 \pmod{p} \tag{10}$

を得ます。

一方、フェルマーの小定理より

$a^p \equiv a \pmod{p}$

です。両辺 $p$ 乗すると

$a^{p^2} \equiv a^p \equiv a \pmod{p}$

が得られ、再度 $p$ 乗すると

$a^{p^3} \equiv a^p \equiv a \pmod{p}$

が得られます。繰り返し適用すると

$a^{p^e} \equiv a \pmod{p} \tag{11}$

が得られます。

$(10)$ と $(11)$ を合わせると $a \equiv 1 \pmod{p}$ を得ますが、これは $p\not\mid (a-1)$ の仮定に反します。

よって、 $p \mid (a-1)$ が示されました。

(ii) $p = 2$ のとき：
$\lambda = 2^e$ のとき $4 \mid (a-1)$ を示します。

$\lambda = 2^e$ のとき

$\displaystyle b\frac{a^{2^e}-1}{a-1} \equiv 0 \pmod{2^e} \tag{12}$

であり、 $(b, 2) = 1$ よりこれは

$\displaystyle \frac{a^{2^e}-1}{a-1} \equiv 0 \pmod{2^e} \tag{13}$

と同値です。

ここで、 $4\not\mid (a-1)$ と仮定すると、① $2\not\mid (a-1)$ であるか ② $2 \mid (a-1)$ かつ $4\not \mid (a-1)$ であるかのいずれかです。

①のとき、 $(13)$ より $a^{2^e} - 1 \equiv 0 \pmod{2^e}$ です。すなわち $a^{2^e} \equiv 1\pmod{2}$ です。一方、①の条件から $a$ は偶数であり、これは $a^{2^e} \equiv 0 \pmod{2}$ であるから矛盾です。

②のとき、 $a \equiv 3 \pmod{4}$ であるから、 $a^2 \equiv 1 \pmod{8}$ です。 $x = a^2, \; y = 1$ として補題2（指数持ち上げ補題）を適用すると

$\operatorname{ord}_2(a^{2^2} - 1^2) = \operatorname{ord}_2(a^2-1) + 1 \geq 4$

また、補題2を $x = a^{2^2}, \; y = 1$ として再度適用すると

$\operatorname{ord}_2(a^{2^3} - 1^2) = \operatorname{ord}_2(a^{2^2}-1) + 1 \geq 5$

繰り返し適用すると

$\operatorname{ord}_2(a^{2^{e-1}} - 1) \geq e+1$

となり

$a^{2^{e-1}} \equiv 1 \pmod{2^{e+1}}$

です。つまり

$a^{2^{e-1}} - 1 \equiv 0 \pmod{2^{e+1}} \tag{14}$

となります。

$\operatorname{ord}_2(a-1) = 1$ より、 $(14)$ の両辺を $a-1$ で割って

$\displaystyle \frac{a^{2^{e-1}} - 1}{a-1} \equiv 0 \pmod{2^{e}} \tag{15}$

が得られます。これは $\lambda = 2^e$ の最小性に矛盾します。

ゆえに、 $4\mid (a-1)$ が示されました。

（ $\Longrightarrow$ の証明終わり）

$\Longleftarrow$ の証明：

$(b, p^e) = 1$ かつ $q \mid (a-1)$ のとき、 $\lambda = p^e$ であることを示します。

補題2（指数持ち上げ補題）を $x = a, \; y = 1$ として適用すると

$\operatorname{ord}_p(a^p - 1) = \operatorname{ord}_p(a - 1) + 1$

また、 $x = a^p, \; y = 1$ として補題2を適用すると

$\begin{align*} \operatorname{ord}_p(a^{p^2} - 1) &= \operatorname{ord}_p(a^p - 1) + 1 \\ &= \operatorname{ord}_p(a - 1) + 2 \end{align*}$

繰り返し補題2を適用すると

$\operatorname{ord}_p(a^{p^g} - 1) = \operatorname{ord}_p(a - 1) + g \tag{16}$

を得ます。

したがって

$\displaystyle \operatorname{ord}_p\left(\frac{a^{p^g} - 1}{a-1}\right) = g \tag{17}$

が得られます。

パラメータ $(a, b, p^e)$ の線形合同法の周期を $\lambda$ とすると

$\displaystyle \frac{a^n - 1}{a-1} \equiv 0 \pmod{p^e} \;\; \Longleftrightarrow \;\; \lambda \mid n \tag{18}$

が成り立ちます。

式 $(17)$ に $g = e$ とすることで

$\displaystyle \frac{a^{p^e} - 1}{a-1} \equiv 0 \pmod{p^e}$

が成立するので、 $(18)$ より $\lambda \mid p^e$ です。すなわち、 $\lambda = p^g$ （ $0\leq g \leq e$ ）であることがわかりました。

式 $(17)$ より $\lambda = p^e$ でなければならないことが結論づけられます。

（定理1の証明終わり）

おわりに

今回は、線形合同法の周期が最大となるような必要十分条件を証明しました。証明は・・・かなり大変でした。

$M = p^e$ のケースに帰着できるということが一つのポイントでした。また、 $M = p^e$ において周期が $\lambda = p^e$ になる条件を示す際には、指数持ち上げ補題をつかうのが面白かったですね。

指数持ち上げ補題については、以前よりせきゅーんさんのブログにて存在は知っていたのですが、いまいち使い所を理解していませんでした。
integers.hatenablog.com

今回、見事にハマる応用例を知ることができて面白かったです。

実は、元々は $R = \mathbb{Z}/M\mathbb{Z}$ としてアフィン群 $R^\times \ltimes R$ における $(a, b)$ の位数から示す方針で考えていたのですが、どうもうまくいきませんでした。結局、 $1 + a + \cdots + a^{n-1}$ を処理する部分がキーになるのですが、 $p \mid (a-1)$ のときに $R$ 内で二項定理が使えないので、うまく証明できませんでした。また気が向いたら考えてみたいと思います。

以前考えていたアフィン群の位数の問題
tsujimotter.hatenablog.com

や、 $\mathbb{Z}/M\mathbb{Z}$ の冪零性の問題
tsujimotter.hatenablog.com

など、過去の話が繋がってきて面白いなと思いました。

いずれにしても $\mathbb{Z}/n\mathbb{Z}$ って面白いですね！　さすがにもう遊びつくしたかなと思っていたのですが、まだまだ楽しめそうな気がします。

それでは今日はこの辺で！

参考文献

指数持ち上げ補題の証明はこちらを参考にさせていただきました。
integers.hatenablog.com

線形合同法の周期で調べていくうちに見つけたブログ記事です。
oupo.hatenadiary.com

実は、Knuth先生の本を早い段階で見つけてしまったので、あまり参考にできていないのですが、 $M = 2^e$ のケースについて証明しているようです。今回やったように素数のべきのケースに帰着できるので、本質的な方法と言えそうですね。ただ、 $p = 2$ のときは、今回やったように大分例外的な議論が必要なので、証明は大変そうです。

そして、一番参考したのはこちらの本です。

The Art of Computer Programming　Volume 2 Seminumerical Algorithms Third Edition 日本語版 (アスキードワンゴ)

作者:Donald E. Knuth,斎藤博昭,長尾高弘,松井祥悟,松井孝雄,山内斉
ドワンゴ

Amazon

他のページも面白そうだなと思ったので、気が向いたら読んでみようと思いました。

ただ、上記の本を購入したいと思っている方へあらかじめ注意を述べておくと、「Kindle版は買わない方がいい」と思います。数式のレイアウトが、かなりひどい状況になっています。紙の本を買いましょう。

おまけ（2021.05.26追記）

$M$ が偶数のとき、線形合同法は偶数・奇数を交互に出力することが知られています。

それが原因で「カルドセプトサーガ」というXbox360向けゲームで「ダイス目が偶数と奇数を繰り返す致命的バグ」が発生し、店頭在庫が回収されることになったとか。
http://www.math.sci.hiroshima-u.ac.jp/m-mat/TEACH/ichimura-sho-koen.pdf