LCGs, Zi=(5Zi-1+3),求解?

（1）
Actually computing Z₀ = 7 , Z1 = 6 , Z2 = 1 , Z3 = 8 , Z4 = 11 , Z5 = 10 , Z6 = 5 , Z7 = 12 , Z8 = 15 ,
Z9 = 14 , Z10 = 9 , Z11 = 0 , Z12 = 3 , Z13 = 2 , Z14 = 13 , Z15 = 4 , Z16 = Z₀ = 7 (full period).
As 500 mod 16 = 4 , we have Z500 = Z4 = 11.

Alternative method:
Zᵢ = (5Zᵢ₋₁+ 3) mod 16 with Z₀ = 7 ,
Say Zᵣ = (5Zᵣ₋₁+ 3) , then Zᵣ ≡ Zᵢ (mod 16).
Zᵣ + k = 5(Zᵣ₋₁+ (3+k)/5) , set k = (3+k)/5 then k = 3/4 , so
Zᵣ + 3/4 = 5(Zᵣ₋₁+ 3/4)
Zᵣ + 3/4 = 5ʳ (Z₀+ 3/4)
Zᵣ = 5ʳ (Z₀+ 3/4) - 3/4 = 5ʳ (7 + 3/4) - 3/4 = (31×5ʳ - 3) / 4 , thus
Z₅₀₀ = (31 × 5^500 - 3) / 4 mod 16
4 Z₅₀₀ = 31 × 5^500 - 3 mod (16×4)
= 31 × (2²+1)^500 - 3 mod 64
= 31 × ( ... + C(500,2) × (2²)² + 500 × 2² + 1 ) - 3 mod 64
= 31 × (500 × 499 × 8 + 2001) - 3 mod 64
= 31 × (- 12 × -13 × 8 + 17) - 3 mod 64
= 31 × (96 × 13 + 17) - 3 mod 64
= 31 × (32 × 13 + 17) - 3 mod 64
= 31 × (32 + 17) - 3 mod 64
= 1516 mod 64
= 44
Therefore, Z₅₀₀ = 44/4 = 11.

（2）
1. Zᵢ = (13Zᵢ₋₁+13) mod 16
記 Zᵣ = (13Zᵣ₋₁+13) , 則 Zᵣ ≡ Zᵢ (mod 16)
Zᵣ + k = 13(Zᵣ₋₁+ (13+k)/13)
令 k = (13+k)/13 , 則 k = 13/12.
Zᵣ + 13/12 = 13(Zᵣ₋₁+ 13/12)
Zᵣ + 13/12 = 13ʳ (Z₀+ 13/12)
Zᵣ = 13ʳ (Z₀+ 13/12) - 13/12
若存在 full period , 則 Zᵣ - Z₀ ≡ 0 (mod 16) 對 1 ≤ r ≤ 15 皆不成立,但對 r = 16 成立。
Zᵣ - Z₀ = 13ʳ (Z₀+ 13/12) - 13/12 - Z₀ = (13ʳ - 1)(Z₀+ 13/12) = (13ʳ - 1)(12Z₀+13) / 12 ,
若 (13ʳ - 1)(12Z₀+13) / 12 ≡ 0 (mod 16) , 則13ʳ - 1 ≡ 0 (mod 12×16), 取 r = 16 測試必要條件:
13^16 - 1 = (13 -1)(13 +1)(13² +1)(13⁴+1)(13^8 +1) ≡ 0 (mod 12×16) 明顯成立,
而對於其他為16因數之r 值, 易知(13 - 1)、(13² - 1)、(13⁴- 1)、(13^8 - 1) 皆不被 12×16 整除,
故使 13ʳ - 1 ≡ 0 (mod 12×16) 的 r 最小正值是16, 這表明 Zᵢ = (13Zᵢ₋₁+13) mod 16 have full period.

2. Zᵢ = (12Zᵢ₋₁+13) mod 16
記 Zᵣ = (12Zᵣ₋₁+13) , 則 Zᵣ ≡ Zᵢ (mod 16)
Zᵣ + k = 12(Zᵣ₋₁+ (13+k)/12)
令 k = (13+k)/12 , 則 k = 13/11 , 得 Zᵣ = 12ʳ (Z₀ + 13/11) - 13/11.
若存在 full period , 則 Zᵣ - Z₀ = 12ʳ (Z₀ + 13/11) - 13/11 - Z₀ = (12ʳ - 1)(Z₀ + 13/11) ≡ 0 (mod 16)
(12ʳ - 1)(11Z₀ + 13) ≡ 0 (mod 11×16) 對 1 ≤ r ≤ 15 皆不成立, 但對 r = 16 成立。 取 r = 1 ,
若 (12 - 1)(11Z₀ + 13) ≡ 0 (mod 11×16) 則必須 11Z₀ + 13 ≡ 0 (mod 16), 由(11,16) | 13 知這樣的Z₀必存在,
因此 (12ʳ - 1)(11Z₀ + 13) ≡ 0 (mod 11×16) 對 r = 1 成立, 這表明 Zᵢ = (12Zᵢ₋₁+13) mod 16沒有 full period.

3. Zᵢ = (13Zᵢ₋₁+12) mod 16
記 Zᵣ = (13Zᵣ₋₁+12) , 則 Zᵣ ≡ Zᵢ (mod 16)
Zᵣ + k = 13(Zᵣ₋₁+ (12+k)/13)
令 k = (12+k)/13 得 k = 1 , 則 Zᵣ = 13ʳ (Z₀+ 1) - 1. 若存在 full period , 則 Zᵣ - Z₀ = 13ʳ (Z₀+ 1) - 1 - Z₀
= (13ʳ - 1)(Z₀+ 1) ≡ 0 (mod 16) 對 1 ≤ r ≤ 15 皆不成立, 但對 r = 16 成立。
無論 r 取值為何, 總有 Z₀ = 15 使之成立, 故 Zᵢ = (13Zᵢ₋₁+12) mod 16 沒有 full period.

4.1. Zᵢ = (Zᵢ₋₁+12) mod 13
考慮 Zᵢ - Z₀ = 12i mod 13 = 0 對 1 ≤ i ≤ 12 皆不成立, 但對 i = 13 成立,
故 Zᵢ = (Zᵢ₋₁+12) mod 13 have full period.