Here is the official solution. We will show that $11$ is the smallest possible value of $n.$ Let $f(a,m)=\frac{a^m+3^m}{a^2-3a+1}$ for $(a,m) \in A \times \mathbb{Z^+}.$ If $a \equiv 5 \pmod{11},$ then $11 \mid a^2-3a+1;$ but $a^m+3^m \equiv 5^m+3^m \equiv 3^m(9^m+1) \not\equiv 0 \pmod{11}$ for all $m \in \mathbb{Z^+}.$ Therefore $f(a,m)$ is not an integer value for any $a \equiv 5 \pmod {11}$ and $m \in \mathbb{Z^+}.$ On the other hand, $f(a,m)$ is an integer for $(a,m)=(-5,20),(-4,14),(-3,1),(-1,2),(0,1),(1,1),(2,1),(3,1),(4,2),(6,9),(7,2),(8,20),(12,9)$ and the proof is done.

why smaller values doesn't provide?

Is $n=10$ satisfy? if we choose $n=10$ then $k=0$ and we have; $ a \equiv 0\pmod{10} \Rightarrow a=10^{\kappa},\kappa \in \mathbb{Z^{+}} \Rightarrow (10^{\kappa}+3)\left( \sum_{\ell =0}^{\kappa m} 10^{(\kappa m-1)-\ell}3^{\ell}\right) \Longrightarrow 10^{\kappa}\not \equiv -3 \pmod{71}, \left( \sum_{\ell =0}^{\kappa m} 10^{(\kappa m-1)-\ell}3^{\ell}\right) \not \equiv 0\pmod{71}$ and we are done.

brdkc43 you are right.