Chapter 4.4, Problem 43E

Use Exercise 41 to deter mine whether $M_{\text{11}}{\text{=2}}^{\text{11}}-\text{1}=\text{2}0\text{47}$ and $M_{\text{17}}={\text{2}}^{\text{17}}-\text{1}\equiv \text{131},0\text{71}$ are prime.

Let n be a positive integer and let $n-\text{1}={\text{2}}^{s}t$ , where s is a nonnegative integer and t is an odd positive integer. We that n passes Miller’s test for the base b if either $b^{\text{t}}\equiv \text{1}\left(\text{mod }n\right)$ or $b^{\text{21}}\equiv -\text{1}\left(\text{mod }n\right)$ for some j with $\text{0}\le j\le s-1$ . It can be shown (see [R010]) that a composite integer n passes Miller’s test for fewer than $n/\text{4}$ bases b with $\text{1}<b<n$ . A composite positive integer n that passes miller’s test to the base b is called a strong pseudoprime to the base b.