已知Xn+1=aXn(mod2k),求{X}最大周期与对应的a值。 说明:对问题中k仅考虑k≥3的情形;当k=0,1,2时,可通过枚举,略。 解: 引理1:欧拉定理; 引理2:模m有原根的必要条件时m=1,2,4,p或2p,其中p是奇素数,∝≥1; (1)设对于某一a值,{Xn}最大周期为T(a),则 XT(a)+1=aT(a)X1 =X1(mod 2k) 即 aT(a)≡1(mod2k) 由引理1:欧拉定理可知φ(2k)=2k-1,则 T(a)2k-1 由引理2知,模2没有原根,则 T(a)≠p(2k),即T(a)≠2k-1 所以 T(a)l2k-2且T(a)≤2k-2 (2)考虑a的取值时,显然a应为奇数,可以分为a=8t士1与a=8t士3两种 情形。 a)当a=8t±3(t∈N)时,可由数学归纳法证明如下结论 T(a)2k-3, 1. 当k=3时, a2k-3=(8t±3)2*-3=(8t±3)2≠1(mod23) Ⅱ.假设k=r时,存在 a2r-3≠1(mod2) 当k=r+1时, a2-2-1=(a2r-3-1)(a2-3+1)
已知𝐗𝐧+𝟏 = 𝐚𝐗𝐧(𝐦𝐨𝐝 𝟐 𝐤 ),求{ Xn }最大周期与对应的 a 值。 说明:对问题中 k 仅考虑 k≥3 的情形;当 k=0,1,2 时,可通过枚举,略。 解: 引理 1:欧拉定理; 引理 2:模 m 有原根的必要条件时 m = 1,2,4,p ∝或2p ∝,其中 p 是奇素数,∝≥ 1; (1) 设对于某一 a 值,{ Xn }最大周期为 T(a),则 XT a +1 ≡ a T(a)X1 ≡ X1(mod 2 k ) 即 a T(a) ≡ 1(mod 2 k ) 由引理 1:欧拉定理可知φ 2 k = 2 k−1,则 T a |2 k−1 由引理 2 知,模 2 k 没有原根,则 T(a) ≠ φ(2 k ),即T(a) ≠ 2 k−1 所以 T a |2 k−2且 T(a) ≤ 2 k−2 (2) 考虑 a 的取值时,显然 a 应为奇数,可以分为 a=8t±1 与 a=8t±3 两种 情形。 a) 当a = 8t ± 3 (t ∈ N)时,可由数学归纳法证明如下结论 T a ∤ 2 k−3, I. 当k = 3时, a 2 k−3 = (8t ± 3) 2 k−3 = (8t ± 3) 2 0 ≠ 1(mod 2 3 ) II. 假设k = r时,存在 a 2 r−3 ≠ 1(mod 2 r ) 当k = r + 1时, a 2 r−2 − 1 = a 2 r−3 − 1 (a 2 r−3 + 1)
由于a2r-3+1(mod2) 所以a2-3-1=2b.Q1,其中b2k-3 再结合(l)中结论可知,在a=8t±3(t∈N时,T(a)=2k-2。 b)当a=8t±1(t∈N)时,由相同方法可知.T(a)≤2k-3。 综上所述,当a=8t±3(t∈N)时,有最大周期2k-2
由于a 2 r−3 ≠ 1(mod 2 r ) 所以a 2 r−3 − 1 = 2 b ∙ Q1,其中b 2 k−3 再结合(1)中结论可知,在a = 8t ± 3 (t ∈ N)时,T a = 2 k−2。 b) 当a = 8t ± 1 (t ∈ N)时,由相同方法可知. T(a) ≤ 2 k−3。 综上所述,当a = 8t ± 3 (t ∈ N)时,有最大周期2 k−2