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.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Ross Millikan Sep 27 '11 at 13:30
  • 7
    $\begingroup$ 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? $\endgroup$ – TMM Sep 27 '11 at 13:30
  • 2
    $\begingroup$ @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. $\endgroup$ – TMM Sep 27 '11 at 13:38
  • 2
    $\begingroup$ @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. $\endgroup$ – Ross Millikan Sep 27 '11 at 13:39
  • 2
    $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Sep 27 '11 at 13:56
2
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Gerry Myerson Apr 22 '12 at 4:52
  • $\begingroup$ Oops! That was indeed a good catch (should have paid more attention) $\endgroup$ – Kirthi Raman Apr 22 '12 at 23:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy