Sequence $x_n$ such that $x_{n}\equiv 0\pmod {27}\Longleftrightarrow n\equiv 3\pmod 9$ Let  $x_{n}$ be a sequence such that  $x_{0}=9,x_{1}=89$,and such
$$x_{n+2}=10x_{n+1}-x_{n}\forall n\ge 0$$
Show that
$$x_{n}\equiv 0\pmod {27}\Longleftrightarrow n\equiv 3\pmod 9$$
Is there a very simple way to prove that a sequence has a period of 9 in the sense of mod 27?
 A: You only need to compute $18$ terms to see that the series repeats $\bmod 27$.  If you reduce $\bmod 27$ at each step you never deal with numbers larger than $297$ so that doesn't take long.  Note that $a_{18}=a_0,a_{19}=a_1$ so the repeat is established.

A: Note the corresponding characteristic equation is
$$ \lambda^2-10\lambda+1=0 $$
which has two roots $r_1=5+2\sqrt6,r_2=5-2\sqrt6$. Therefore $x_n$ can be expressed as
$$ x_n=C_1r_1^n+C_2r_2^n. $$
Using $x_0=9,x_1=89$, it is easy to see $C_1=\frac92+\frac{11}{\sqrt6},C_2=\frac92-\frac{11}{\sqrt6}.$ So
\begin{eqnarray}
x_n&=&\bigg(\frac92+\frac{11}{\sqrt6}\bigg)(5+2\sqrt6)^n+\bigg(\frac92-\frac{11}{\sqrt6}\bigg)(5-2\sqrt6)^n\\
&=&\frac92\bigg[(5+2\sqrt6)^n+(5-2\sqrt6)^n\bigg]+\frac{11}{\sqrt6}\bigg[(5+2\sqrt6)^n-(5-2\sqrt6)^n\bigg]\\
&=&9\sum_{2k\le n}\binom{n}{2k}5^{n-2k}6^k+22\sum_{2k-1\le n}\binom{n}{2k-1}5^{n-2k+1}6^{k-1}\\
&\equiv&9\cdot5^n+22\bigg[\binom{n}{1}5^{n-1}+\binom{n}{3}5^{n-3}6\bigg]\mod27\\
&\equiv&5^{n-3}\bigg[9\cdot5^3+22n\cdot5^2+22n(n-1)(n-2)\bigg]\mod27\\
&\equiv&-9+10n-5n(n-1)(n-2)\mod27
\end{eqnarray}
Clearly if $x_n\equiv0\mod27$, then $3|n$ since $3|n(n-1)(n-2)$. Let $n=3k$. Then
\begin{eqnarray}
x_n&\equiv&-9+10n-5n(n-1)(n-2)\mod27\\
&\equiv&-9+30k-15k(3k-1)(3k-2)\mod27\\
&\equiv&3\bigg[-3-15k(9k^2-9k+4)\bigg]\mod27\\
&\equiv&3(-3-60k)\mod27\\
&=&-9(20k+1)\mod27\\
\end{eqnarray}
Thus if $x_n\equiv0\mod27$, then $3|(20k+1)$ which implies that $k=3l+1$ or 
$$ n\equiv3\mod 9$$
Conversely if $ n\equiv3\mod 9$, it is not hard to show $x_n\equiv0\mod27$.
