§4.1 — a primitive root gives period m − 1
ProvedCarryRNG.SWB.primitive_root_expansion_periodnumber-theoryp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1periodic-expansionrandom-number-generationsubtract-with-borrow
Let be prime, be relatively prime to , and . Suppose the order of modulo is , so is a primitive root. Then, for every positive integer , the base- digits of satisfy
Thus every proper fraction with this denominator has least digit period .
Preamble
import Definitions.Def_CarryRNG_AWC_digit
Formal statement
namespace CarryRNG.SWB
/-- Section 4.1: a primitive root gives full period `m - 1` for each proper fraction. -/
theorem primitive_root_expansion_period (b m k p : ℕ) (hb : 2 ≤ b) (hm : m.Prime)
(hk : 0 < k ∧ k < m) (hbm : Nat.Coprime b m)
(hprim : orderOf (b : ZMod m) = m - 1) (hp : 0 < p) :
(∀ j : ℕ, 1 ≤ j → CarryRNG.AWC.digit b m k (j + p) = CarryRNG.AWC.digit b m k j) ↔
m - 1 ∣ p := by sorry
end CarryRNG.SWB
Source
G. Marsaglia and A. Zaman, A new class of random number generators, Ann. Appl. Probab. 1 (1991), p. 467, Section 4.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.