乗算型合同法の周期

命題 3.6（「擬似乱数生成器」§3）・ ✓公理まで証明済み

乗算型合同法 $x_{k+1} = ax_k \bmod m$ について次が成り立つ。

$\gcd(a, m) = \gcd(x_0, m) = 1$ ならば、列 $(x_k)$ は純周期的で周期は $\mathrm{ord}_m(a)$ である。
$m = 2^e$ （ $e \ge 3$ ）で $a$ が奇数のとき、 $\mathrm{ord}_{2^e}(a) \le 2^{e-2}$ であり、 $a \equiv 3$ または $5 \pmod 8$ ならば等号が成り立つ。 $e \ge 4$ のときは、等号が成り立つのはこの場合に限る。
$m = p$ が素数で $p \nmid a$ のとき、 $\mathrm{ord}_p(a)$ は $p - 1$ の約数であり、 $p - 1$ に等しいのは $a$ が $p$ を法とする原始根のとき、かつそのときに限る。原始根は必ず存在する。

本文で読む（証明と前後の説明）→

閉包の状態

✓ 公理まで証明済み

証明が使う定理を前提としてたどると、Rikai の中の証明だけで定義・公理（物理では基本仮定）までつながっています（前提の定理類 25 件、定義なども含めて 29 件）。

印の意味: ✓公理まで証明済み・ △証明あり（閉包未完）・ ※主張のみ。テーマごとの集計は閉包の状況。

前提をたどる証明が使う定理・定義（直接 10 件）

▸ を開くと、その項目の証明が使う前提が出ます。深い先は各項目のページでたどれます。

線形合同法の閉じた形✓補題 3.2・擬似乱数生成器
- 合同式の四則✓命題 3.3・合同式とフェルマーの小定理
命題 4.4✓合同式とフェルマーの小定理
- ベズーの等式✓定理 2.2・合同式とフェルマーの小定理
  - 除法の原理✓定理 2.1・合同式とフェルマーの小定理
    整列性公理 3.1・証明の技術
有限状態の生成器は最終的に周期的✓命題 2.3・擬似乱数生成器
消去法則✓命題 3.6・合同式とフェルマーの小定理
- ユークリッドの補題✓補題 2.3・合同式とフェルマーの小定理
  - ベズーの等式✓定理 2.2・合同式とフェルマーの小定理（上で展開済み）
等比和の p 進付値✓補題 3.3・擬似乱数生成器
- 合同式の四則✓命題 3.3・合同式とフェルマーの小定理
- 付値の規則と gcd・lcm✓命題 5.3・整除と素因数分解（上で展開済み）
付値の規則と gcd・lcm✓命題 5.3・整除と素因数分解
- 素因数分解の指数による表示✓定理 5.2・整除と素因数分解
  - ユークリッドの補題✓補題 4.1・素数の魅力と素数定理
    素数と合成数定義 2.2・素数の魅力と素数定理
    ベズーの等式✓補題 2.4・素数の魅力と素数定理この先をたどる →
  - 算術の基本定理✓定理 4.2・素数の魅力と素数定理
    完全帰納法✓定理 4.3・証明の技術この先をたどる →
    素数と合成数定義 2.2・素数の魅力と素数定理
    ユークリッドの補題✓補題 4.1・素数の魅力と素数定理（上で展開済み）
フェルマーの小定理✓定理 5.1・合同式とフェルマーの小定理
- ユークリッドの補題✓補題 2.3・合同式とフェルマーの小定理（上で展開済み）
- 消去法則✓命題 3.6・合同式とフェルマーの小定理（上で展開済み）
- 合同式の四則✓命題 3.3・合同式とフェルマーの小定理
位数による冪の判定✓定理 6.3・群論入門
原始根定義 2.4・原始根と平方剰余の相互法則
素数を法とする原始根の存在✓定理 2.5・原始根と平方剰余の相互法則
- 位数の基本性質✓補題 2.2・原始根と平方剰余の相互法則
  - 互いに素な商✓補題 2.3・整除と素因数分解
  - ユークリッドの補題✓補題 2.3・合同式とフェルマーの小定理（上で展開済み）
- 素数を法とする根の個数✓補題 2.3・原始根と平方剰余の相互法則
- 約数についての和✓定理 7.5・整除と素因数分解

これを使っている定理

証明で明示的に参照している定理は、まだありません。

乗算型合同法の周期

閉包の状態

前提をたどる 証明が使う定理・定義（直接 10 件）

これを使っている定理

関連するノック 2 問

前提をたどる証明が使う定理・定義（直接 10 件）