第3問

第3段階より、数列 $(a_i\bmod p)$ は周期 $k$ と $k+p$ を持つ。$p\nmid k$ なので $\gcd(k,k+p)=\gcd(k,p)=1$ であり、互いに素な2つの周期を持つ数列はそれらの最大公約数、すなわち $1$ を周期として持つ。つまり任意の $i$ について $p\mid a_{i+1}-a_i$ である。