Лемма 2. Пусть s=s₀s₁… - произвольная л.р.п. n-го порядка над полем F. Тогда для любого целого t ≥ 0 существуют a₀, a₁, …, a_n–1 в F, что для всех i ≥ 0 справедливо:

si+t  = .

(3)

Доказательство. Если t < n, то требуемые равенства верны при a_t  = 1 и a_j  = 0 для j ≠ t. При t ≥ n они доказываются индукцией по t, ибо при t = n они верны в силу (2) и по предположению индукции можно записать:

si+t+1  = si+1+t = , i ≥ 0.

(4)

Для каждого j = 0, 1, …, n-1 выполняется j+1 ≤ n, поэтому по предположению индукции для любого такого j существуют b₀, b₁, …, b_n–1 в F, что для всех i ≥ 0

После замены в (4) каждого s_i+1+j равным ему выражением последнего вида, получим требуемые равенства для s_i+t+1.

Пусть далее s = s₀s₁… есть m-последовательность n-го порядка над полем F = Z_p, т.е. q = p и членами в s являются числа 0, 1, …, p-1.

Лемма 3. Пусть aF, a ≠ 0 и t ≥ 0. Тогда для высказываний:

(i) s_i+t = as_i для всех i ≥ 0;

(ii) t = 0 mod (1 + p + p² + … + p^n–1)

справедливы следующие утверждения: (i) (ii) и t ≤ pⁿ−2[(i) & (ii)].

Доказательство. Пусть верно (i). Тогда ввиду теоремы Ферма s_i+(p–1)t = a^p–1s_i = s_i для всех i ≥ 0, что возможно только при условии, что (p-1)t кратно периоду последовательности s, т.е. (p-1)t = k(pⁿ -1) для некоторого целого k, откуда t = k(pⁿ -1)/(p-1) = k(1 + p + p² + … + p^n–1), т.е. верно (ii).

Для доказательства второго утверждения вычислим вектор (as₀) (as₁) … (as_n–1). По лемме 1 это будет вектор s_ts_t+1…s_t+n–1 для некоторого t ≤ pⁿ−2, т.е. s_t = as₀, s_t+1= as₁, …, s_t+n–1= as_n–1. Применяя далее индукцию по i, предположим, что s_i+t = as_i+0, s_i+t+1 = as_i+1, …, s_i+t+n–1 = as_i+n–1 для некоторого i ≥ 0, и, пользуясь (2), запишем:

Этим доказано (i). Из него по предыдущему следует (ii).