3.4 Periodicity
For any \(k \in \mathbb {N}\) and \(m, n \in \mathbb {N}\), if \(m \equiv n \pmod{2^k}\), then \(E(k, m) = E(k, n)\).
By induction on \(k\). The base case \(k=0\) is trivial as \(E(0, n)\) is the empty function. For the inductive step \(k+1\), if \(m \equiv n \pmod{2^{k+1}}\), then \(m \equiv n \pmod2\), so \(X(m) = X(n)\). By the congruence properties of \(T\) (Lemma 80), \(T(m) \equiv T(n) \pmod{2^k}\). By the induction hypothesis, \(E(k, T(m)) = E(k, T(n))\), which implies agreement on the remaining \(k\) entries of the parity vector.
For \(m, n \ge 1\), if \(E(k, m) = E(k, n)\), then \(m \equiv n \pmod{2^k}\).
Assume \(E(k, m) = E(k, n)\). Then \(Q(k, m) = Q(k, n) = S\) and \(Q(k, m) = Q(k, n) = Q\). From the linear decomposition (Lemma 100), we have:
Subtracting these yields \(2^k (T^k(m) - T^k(n)) = 3^S (m - n)\). Since \(2^k\) is coprime to \(3^S\) (Lemma 12), \(2^k\) must divide \(m - n\), so \(m \equiv n \pmod{2^k}\).
(Theorem 1.2 in Terras (1976) [ 6 ] ) Two positive integers \(m, n \ge 1\) have the same parity vector of length \(k\) if and only if they are congruent modulo \(2^k\):