情報科学 › 乱数と確率的数値計算 › 擬似乱数生成器

等比和の p 進付値

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

$p$ を素数、 $a \ge 1$ を整数とし、 $a \equiv 1 \pmod p$ とする。 $p = 2$ のときはさらに $a \equiv 1 \pmod 4$ とする。このとき、すべての整数 $k \ge 1$ について

v_p\bigl(S_k(a)\bigr) = v_p(k)

が成り立つ。

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

閉包の状態

✓ 公理まで証明済み

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

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

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

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

合同式の四則✓命題 3.3・合同式とフェルマーの小定理
付値の規則と gcd・lcm✓命題 5.3・整除と素因数分解
- 素因数分解の指数による表示✓定理 5.2・整除と素因数分解
  - ユークリッドの補題✓補題 4.1・素数の魅力と素数定理
    素数と合成数定義 2.2・素数の魅力と素数定理
    ベズーの等式✓補題 2.4・素数の魅力と素数定理この先をたどる →
  - 算術の基本定理✓定理 4.2・素数の魅力と素数定理
    完全帰納法✓定理 4.3・証明の技術この先をたどる →
    素数と合成数定義 2.2・素数の魅力と素数定理
    ユークリッドの補題✓補題 4.1・素数の魅力と素数定理（上で展開済み）

これを使っている定理証明で参照している 2 件

Hull–Dobell の定理✓定理 3.4・擬似乱数生成器
乗算型合同法の周期✓命題 3.6・擬似乱数生成器

関連するノック 1 問

乱数と確率的数値計算第 2 問