Show that the following are prime:
(a) $M_{13} = 2^{13} - 1$
(b) $M_{17} = 2^{17}− 1$
(a) Any prime factor of $M_{13}$ must be less than or equal to $\lfloor \sqrt{2^{13}-1} \rfloor = 90$. So we only need to test factors up to 90.
By Proposition 4.23, we know that any prime factor $p$ must be of the form $p=2k(13)+1$, where $k$ is an integer.
By Proposition 4.24, we know that any prime factor must be congruent to $\pm 1 \pmod 8$.
The following table lists the primes up to 90, and tests their conformance to these two conditions.
| p | (p-1) mod (2*13) | p mod 8 |
| 2 | 1 | 2 |
| 3 | 2 | 3 |
| 5 | 4 | 5 |
| 7 | 6 | 7 |
| 11 | 10 | 3 |
| 13 | 12 | 5 |
| 17 | 16 | 1 |
| 19 | 18 | 3 |
| 23 | 22 | 7 |
| 29 | 2 | 5 |
| 31 | 4 | 7 |
| 37 | 10 | 5 |
| 41 | 14 | 1 |
| 43 | 16 | 3 |
| 47 | 20 | 7 |
| 53 | 0 | 5 |
| 59 | 6 | 3 |
| 61 | 8 | 5 |
| 67 | 14 | 3 |
| 71 | 18 | 7 |
| 73 | 20 | 1 |
| 79 | 0 | 7 |
| 83 | 4 | 3 |
| 89 | 10 | 1 |
| 97 | 18 | 1 |
We can see that only prime $p=79$ conforms to these 2 conditions, and so is the only candidate.
However, using a calculator we can see that $79$ does not divide $2^{13}-1$.
These leaves no candidates as a prime factor of $M_{13}$ and so it is a prime itself.
(b) Any prime factor of $M_{17}$ must be less than or equal to $\lfloor \sqrt{2^{17}-1} \rfloor = 362$. So we only need to test factors up to 362.
By Proposition 4.23, we know that any prime factor $p$ must be of the form $p=2k(17)+1$, where $k$ is an integer.
By Proposition 4.24, we know that any prime factor must be congruent to $\pm 1 \pmod 8$.
The following table shows only the primes up to 90, which confirm to these two tests.
| p | (p-1) mod (2*17) | p mod 8 |
| 103 | 0 | 7 |
| 137 | 0 | 1 |
| 239 | 0 | 7 |
Using a calculator, we can see that none of these primes 103, 137, and 239 divide $M_{17}$.
Since there are no remaining candidates, $M_{17}$ is a prime.