3.2.1 線性同餘法 證明：在形如X[n+1]=(aX[n]+c)%m的遞推式中,如果a,m互素，則X[0]将總是出現在周期中。

遞推式是這樣的 X[n+1]=(aX[n]+c)%m, X[0]是初始的X,顯然X[0]<m。

那麼代入遞推式，X[n] = (a^n*X[0] + c*( 1 + a + a^2 +...+a^n-1) )%m = (X[0]*a^n)%m + (c * ( a^n - 1 ) / ( a - 1 ) ) % m  (*)。

因為gcd(a,m)=1,根據歐拉定理a^φ(m)≡1(mod m)。是以在(*)式中，取n=m*φ(m)，那麼：

 (X[0]*a^n)%m=(X[0]*( a^φ(m) )^m )%m =(X[0]*1^m )%m = X[0].

對( c * ( a ^(mφ(m)) - 1 ) / ( a - 1 ) ) % m的變化要複雜些。專門看：

a ^(mφ(m)) - 1 = ( a^φ(m) )^m - 1 = ( a^φ(m) - 1 )*(1 + a^φ(m) + a^2φ(m) +...+a^(m-1)φ(m) )。而a^kφ(m)≡1(mod m)，是以：

( c * ( a ^(mφ(m)) - 1 ) / ( a - 1 ) ) % m = ( c *  ( a^φ(m) - 1 )*(1 + a^φ(m) + a^2φ(m) +...+a^(m-1)φ(m) ) / ( a - 1)  ) %m

=( c * ( a^φ(m) - 1 )*(1 + 1 + 1 +...+1 ) / (a - 1) ) % m。注意這裡1+1+1+1...+1裡恰好有m個1。是以：

=(c *  ( a^φ(m) - 1 ) / ( a- 1 ) * m ) %m。顯然φ(m) ≥2,則 ( a^φ(m) - 1 ) / ( a- 1 )是個整數。

=0

是以，當n=m*φ(m)時，必有X[n]=X[0]。雖然m*φ(m)不是最小周期，但至少證明了這個問題。

不知道證明過程有沒有誤，或者能搞出更小的周期。望衆高手指教。