线性同余生成器（LCG）最大周期长度证明技术问询

Alright, let's walk through this proof without leaning on the Hull-Dobell theorem, starting with the distinct primes case (p≠q) since you noted that's more straightforward. First, remember that the maximum period for an LCG modulo (m) means the sequence visits every residue from (0) to (m-1) exactly once before repeating—so the total length is (m).

Key Setup: Chinese Remainder Theorem (CRT) #

Since (m=pq) and (p,q) are distinct primes, CRT tells us that the behavior of the LCG modulo (m) is entirely determined by its behavior modulo (p) and modulo (q). If we can show the LCG has maximum period (p) modulo (p) and maximum period (q) modulo (q), then the combined sequence modulo (pq) will have period (\text{lcm}(p,q)=pq=m) (the maximum possible), because (p) and (q) are coprime.

Case 1: Distinct Primes (p≠q) #

Let's analyze the LCG modulo (p) first:

• Condition 2 says (p \mid (a-1)), so (a ≡ 1 \pmod{p}).
• Condition 1 says (\gcd(b,m)=1), which implies (\gcd(b,p)=1) (since (p) divides (m)).

The LCG modulo (p) simplifies to:

x_i ≡ x_{i-1} + b \pmod{p}

Expanding this recurrence, we get (x_i = x_0 + i \cdot b \pmod{p}). Now, since (\gcd(b,p)=1), (b) acts as a generator of the additive group modulo (p). That means as (i) increases from (0) to (p-1), (i \cdot b) takes every value from (0) to (p-1) modulo (p). So the sequence modulo (p) visits all residues exactly once before repeating—its period is (p), the maximum possible for modulo (p).

We can apply the exact same logic to the LCG modulo (q):

• Condition 2 gives (a ≡1 \pmod{q})
• Condition 1 gives (\gcd(b,q)=1)

The modulo (q) sequence is (x_i = x_0 + i \cdot b \pmod{q}), which also has maximum period (q).

By CRT, each pair of residues ((r_p \pmod{p}, r_q \pmod{q})) maps to exactly one residue modulo (pq). Since the modulo (p) and modulo (q) sequences each hit all their residues, the combined sequence modulo (pq) must hit every residue exactly once—so its period is (pq=m), the maximum possible.

Case 2: Equal Primes (p=q) (i.e., (m=p^2)) #

Now let's cover the case where (p=q), so (m=p^2). We need to handle two subcases: (p=2) (so (m=4)) and odd primes (p).

Subcase 2a: (m=4) (Condition 3 applies) #

• Condition 3 says if (4 \mid m), then (4 \mid (a-1)), so (a ≡1 \pmod{4}).
• Condition 1 says (\gcd(b,4)=1), so (b) is odd (1 or 3 modulo 4).

The LCG simplifies to (x_i = x_{i-1} + b \pmod{4}). Since (b) is coprime to 4, adding (b) repeatedly cycles through all 4 residues: for example, if (b=1), the sequence is (x0, x0+1, x0+2, x0+3, x0, ...); if (b=3), it's (x0, x0+3, x0+2, x0+1, x0, ...). Either way, the period is 4, the maximum possible.

Subcase 2b: Odd Prime (p), (m=p^2) #

• Condition 2 says (p \mid (a-1)), so let (a=1 + kp) for some integer (k).
• Condition 1 says (\gcd(b,p^2)=1), so (b) is coprime to (p).

The LCG recurrence is (x_i = (1+kp)x_{i-1} + b \pmod{p^2}). We can derive the closed-form solution for this:

x_i = x_0 \cdot a^i + b \cdot \frac{a^i - 1}{a - 1} \pmod{p^2}

Since (a=1+kp), we can expand (a^i) using the binomial theorem (ignoring terms with (p^2) or higher, since we're working modulo (p^2)):
(a^i ≡ 1 + i \cdot kp \pmod{p^2})

Substituting back into the closed-form, (\frac{a^i -1}{a-1} = \frac{i \cdot kp}{kp} + \text{terms with } p ≡ i + \frac{kp \cdot i(i-1)}{2} \pmod{p^2}). Since (p) is odd, (2) has an inverse modulo (p), but the key point is this term is congruent to (i \pmod{p}), and to get it congruent to (0 \pmod{p^2}), we need (i ≡0 \pmod{p^2}).

Because (\gcd(b,p^2)=1), the only way (x_i ≡x_0 \pmod{p^2}) is if (\frac{a^i -1}{a-1} ≡0 \pmod{p^2}), which requires (i=p^2). So the sequence has period (p^2=m), the maximum possible.

Putting It All Together #

For any (m=pq) (where (p,q) are primes, distinct or equal), the three given conditions ensure that:

• For each prime power factor of (m), the LCG modulo that factor reaches its maximum possible period.
• By CRT (for distinct primes) or direct analysis (for prime squares), the combined sequence modulo (m) reaches the maximum period (m).

内容的提问来源于stack exchange，提问作者pls_halp