2. Let $a_{1}, a_{2}, \ldots$ be a sequence of integers defined by $a_{1}=3, a_{2}=3$, and
$$
a_{n+2}=a_{n+1} a_{n}-a_{n+1}-a_{n}+2
$$
for all $n \geq 1$. Find the remainder when $a_{2020}$ is divided by 22 .
2. Let $a_{1}, a_{2}, \ldots$ be a sequence of integers defined by $a_{1}=3, a_{2}=3$, and
$$
a_{n+2}=a_{n+1} a_{n}-a_{n+1}-a_{n}+2
$$
for all $n \geq 1$. Find the remainder when $a_{2020}$ is divided by 22 .

Solution 1: Let $\left\{F_{n}\right\}_{n=1}^{\infty}=\{1,1,2,3,5,8, \ldots\}$ be the sequence of Fibonacci numbers. We first claim that $a_{n}=2^{F_{n}}+1$ for all $n \in \mathbb{N}$. Clearly, this is true for $n=1,2$. Let $k \in \mathbb{N}$ and suppose that the claim is true for $n=k$ and for $n=k+1$. Then
$$
\begin{aligned}
a_{k+2} & =a_{k+1} a_{k}-a_{k+1}-a_{k}+2 \\
& =\left(a_{k+1}-1\right)\left(a_{k}-1\right)+1 \\
& =2^{F_{k+1}} 2^{F_{k}}+1 \\
& =2^{F_{k+2}}+1 .
\end{aligned}
$$

By strong induction, the claim is proved. Therefore, we now find the remainder when $2^{F_{2020}}+1$ is divided by 22 . To this end, it is easier to find residues modulo 2 and modulo 11 and process them to get the residue modulo 22 (e.g. through Chinese Remainder Theorem).

Clearly, $2^{F_{2020}}$ is even, i.e., $2^{F_{2020}}+1 \equiv 1(\bmod 2)$. We will see later that $2^{F_{2020}}+1 \equiv 0(\bmod$ 11). Therefore, by Chinese Remainder Theorem, $a_{2020}=2^{F_{2020}}+1 \equiv 11(\bmod 22)$.

There are several ways to find the residue of $2^{F_{2020}}+1(\bmod 11)$.
Way 1.1: By Fermat's Little Theorem, $2^{10} \equiv 1(\bmod 11)$. This prompts us to consider the sequence of residues of $F_{n}(\bmod 10)$ in order to find $F_{2020}(\bmod 10)$ :
$$
\begin{array}{c}
\left\{F_{n}(\bmod 10)\right\}_{n=1}^{\infty}=\{1,1,2,3,5,8,3,1,4,5,9,4,3,7,0,7,7,4,1,5,6,1,7,8,5,3,8,1,9,0,9,9,8 \\
7,5,2,7,9,6,5,1,6,7,3,0,3,3,6,9,5,4,9,3,2,5,7,2,9,1,0, \ldots c y c l e\}
\end{array}
$$

We see that the sequence is cyclic with period 60 . Therefore, since $2020=60(33)+40$, we obtain $F_{2020} \equiv 5(\bmod 10)$. Consequently, for some $k \in \mathbb{Z}$,
$$
2^{F_{2020}}+1=2^{10 k+5}+1 \equiv\left(2^{10}\right)^{k} 2^{5}+1 \equiv 33 \equiv 0(\bmod 11) .
$$

Way 1.2: Another way to find $F_{2020}(\bmod 10)$ is to get the residues of $F_{2020}$ modulo 2 and 5 and process them to find the residue modulo 10. Again, we list down the sequence of residues modulo 2 and 5: $\left\{F_{n}(\bmod 2)\right\}_{n=1}^{\infty}=\{1,1,0, \ldots c y c l e\}$ which has period 3 , and
$$
\left\{F_{n}(\bmod 5)\right\}_{n=1}^{\infty}=\{1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,1,0, \ldots c y c l e\},
$$
which has period 20 . Since, $2020 \equiv 1(\bmod 3)$ and $2020 \equiv 0(\bmod 20)$, then $F_{2020} \equiv 1(\bmod 2)$ and $F_{2020} \equiv 0(\bmod 5)$. Therefore, $F_{2020} \equiv 5(\bmod 10)$ by Chinese Remainder Theorem. Thus, (2) holds.

Solution 2: Inspired by the factorization in (1), we define $b_{n}=a_{n}-1$ for all $n \in \mathbb{N}$. Then $b_{1}=b_{2}=2$ and (1) simplifies to
$$
b_{n+2}=b_{n+1} b_{n} .
$$

We observe that $b_{1}=2^{F_{1}}, b_{2}=2^{F_{2}}$, and (3) implies $b_{3}=2^{F_{3}}$. This pattern continues and obviously shows that $b_{n}=2^{F_{n}}$ for all $n \in \mathbb{N}$. Very similar arguments to Solution 1 will give $b_{2020} \equiv 0(\bmod 2)$ and $b_{2020} \equiv 10(\bmod 11)$. Therefore, by Chinese Remainder Theorem, $b_{2020} \equiv 10(\bmod 22)$. Equivalently, $a_{2020} \equiv 11(\bmod 22)$.

Solution 3: By bashing, we can list down the residues of $\left\{a_{n}\right\}_{n=1}^{\infty}$ (or of $\left\{b_{n}\right\}_{n=1}^{\infty}$ as defined in Solution 2):
$$
\begin{array}{l}
\left\{a_{n}(\bmod 22)\right\}_{n=1}^{\infty}=\{3,3,5,9,11,15,9,3,17,11,7,17,9,19,13,19,19,17,3,11,21,3,19,15, \\
11,9,15,3,7,13,7,7,15,19,11,5,19,7,21,11,3,21,19,9,13,9,9,21,7,11 \text {, } \\
17,7,9,5,11,19,5,7,3,13, \ldots c y c l e\} \text {. } \\
\end{array}
$$

Since the sequence is cyclic with period 60 , and $2020 \equiv 40(\bmod 60)$, then $a_{2020} \equiv 11(\bmod 22)$.