3
$\begingroup$

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.

  • 2
    Just to make sure: for $91$ to be a pseudoprime w.r.t the 'witness' $3$ you are supposed to check that $3^{90}\equiv 1\pmod{91}$. You are half way there. To do the other half I recommend looking at $3^3$ modulo $13$. Also, please follow the recommendations from Thijs and Ross. You are very welcome to ask for clarifications to answers, but leaving all answers unaccepted without giving a reason turns potential answerers away.2011-09-27

1 Answers 1

2

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*} $

  • 0
    Oops! That was indeed a good catch (should have paid more attention)2012-04-22