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.

  • 0
    When you have multi-character exponents, arguments of pmod, sqrt, or limits on integrals and sums you need to include them in brackets. So 3^{91} produces $3^{91}$ instead of $3^91$2011-09-27
  • 1
    I believe Theorem 2.4.5 will assure you that $3^{12} \equiv 1 \pmod{13}$, you don't have to assume it. You haven't proven that $3^6 \equiv 1 \pmod {13}$. If you get that, you are home.2011-09-27
  • 7
    This is your 41st question, and you have only 3 accepted answers. Why do you keep coming back, if you think all our answers are bad?2011-09-27
  • 0
    @Thijs: Oh, so if I don't mark as accepted, then it is automatically assumed that I regard those answers as bad? Mainly this custom is because I don't understand answers or that there are something that I don't understand.2011-09-27
  • 0
    I don't understand the downvote. It seems a well-posed question to me showing some effort.2011-09-27
  • 2
    @alv: If one of the answers answers your question, you should accept it. Whether it is right away or after you have gotten clarification in the comments. But not doing so implies the question is still open, and no one has given a satisfactory answer yet.2011-09-27
  • 2
    @alvoutila: If you don't understand an answer, you can comment on it requesting further explanation. People are generally quite willing to work with you in that way, as it is easy to assume more background than a poster has or to write too quickly. It is nice to give a thank-you of acceptance if an answer does resolve your problem.2011-09-27
  • 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
    The calculations are correct, and they do yield the desired result, but OP specifically asked (some months ago) for a solution using Lemma 2.3.3 and Fermat's little theorem, and this answer uses neither.2012-04-22
  • 0
    Oops! That was indeed a good catch (should have paid more attention)2012-04-22