The given problem:
Use Lemma 2.3.3 together with Fermat's little theorem to show that 91
is a pseudoprime to the base 3.
Lemma 2.3.3.
Let $m_1 \dots m_r \in $ N. If $a \equiv b \pmod {m_i}$, $\forall i =1, \dots, r$, then $a \equiv b \pmod {{\rm lcm}(m_1, \dots, m_r)}$. (If $\gcd(m_i, m_j)=1$ when $i \neq j$, so $a \equiv b \pmod {m_1 \dots m_r}$.)
Theorem 2.4.5 (Fermat's little theorem II).
Let $p$ prime and $a \in$ Z such that $p \nmid a$. Then
$a^{p-1} \equiv 1 \pmod p$.
My own attempt:
Because $91=7 \cdot 13$, the number is composite.
According to Theorem 2.4.5 $3^6 \equiv 1 \pmod 7$. On the other hand $90 = 6 \cdot 15 $, so
$3^{90} = 3^{6 \cdot 15} = (3^6)^{15} \equiv 1^{15} \equiv 1 \pmod 7$
Then let's assume according to Theorem 2.4.5 that
$3^{12} \equiv 1 \pmod {13}$. On the other hand $90=12 \cdot 7+6$.
So $3^{90}=3^{12\cdot7+6}=3^{12\cdot7}\cdot 3^6 = (3^{12})^7\cdot3^6 \equiv 1^7 \cdot 3^6 \equiv 1 \pmod {13}$. So according to Lemma 2.3.3 we have $3^{90} \equiv 1 \pmod {91}$ so $3^{91} \equiv 3 \pmod {91}$.
So 91 would be a pseudoprime to the base 3.
Best Answer
Powers of $3$ cycle as follows
$$ \begin{array}{|c|c|c|} n&3^n&3^n \mod 91\\ \hline\\ 1 & 3 & 3\\ 2 & 9 & 9\\ 3 & 27 & 27\\ 4 & 81 & 81\\ 5 & 243 & 61\\ 6 & 729 & 1\\ \hline \end{array} $$
Therefore, since $90 = 6 \times 15$
$$ \begin{align*} 3^{90} &\equiv 1 \hspace{4pt} (\mod 91)\\ \Rightarrow 3^{91} &\equiv 3 \hspace{4pt} (\mod 91) \end{align*} $$