Determine a prime factor of the following composite Mersenne numbers $M_q$:
(a) $M_{43}$
(b) $M_{73}$
We remind ourselves of Proposition (4.23). Let $q$ be an odd prime. Any prime factor $p$ of the composite Mersenne $M_q = 2^q− 1$ is of the form $p= 2kq + 1$ where $k$ is an integer.
Note that this does not mean all primes of the form $p=2kq+$ are factors of $M_q$. It means that those that are factors, have this form. That is, factor implies form, not form implies factor.
We also remind ourselves of Proposition (4.24). Let $q$ be an odd prime. Any prime factor $p$ of $M_q = 2^q -1 $ is of the form $p \equiv \pm 1 \pmod 8$.
Again, this not mean all primes of the form are factors, only that factors have this form.
(a) $M_{43}=2^{43}-1$.
We can't use Proposition (4.19)(a), because setting $n=43$ gives $p=2(43)+1=87$ which is not prime.
We can't use Corollary (4.21) because $43$ is not a Germain prime as $2(43)+1=87$ is not prime.
Let's try finding candidates that conform to propositions (4.23) and (4.24), which are necessary but not sufficient conditions.
The following table shows values of $p=2k(43)+1$, whether it is prime, and $p \mod 8$.
| k | p=2k(43)+1 | prime? | p mod 8 |
| 1 | 87 | no | 7 |
| 2 | 173 | yes | 5 |
| 3 | 259 | no | 3 |
| 4 | 345 | no | 1 |
| 5 | 431 | yes | 7 |
| 6 | 517 | no | 5 |
| 7 | 603 | no | 3 |
We can see $k=5$ gives $p=431$, which is prime, and is congruent to -1 modulo 8, and so is a candidate factor of $2^{43}-1$.
Using a calculator confirms that $431 \mid 2^{43}-1$. And so 431 is a prime factor of $2^{43}-1$.
(b) $M_{73}=2^{43}-1$.
We can't use Proposition (4.19)(a), because setting $n=73$ gives $p=2(73)+1=147$ which is not prime.
We can't use Corollary (4.21) because $73$ is not a Germain prime as $2(73)+1=147$ is not prime.
Let's try finding candidates that conform to propositions (4.23) and (4.24), which are necessary but not sufficient conditions.
The following table shows values of $p=2k(73)+1$, whether it is prime, and $p \mod 8$.
| k | p=2k(73)+1 | prime? | p mod 8 |
| 1 | 147 | no | 3 |
| 2 | 293 | yes | 5 |
| 3 | 439 | yes | 7 |
| 4 | 585 | no | 1 |
| 5 | 731 | no | 3 |
| 6 | 877 | yes | 5 |
| 7 | 1023 | no | 7 |
We can see $k=3$ gives $p=439$, which is prime and also congruent to -1 modulo 8, an so is a candidate factor of $2^{73}-1$.
Using a computer algebra system (link) confirms $439 \mid 2^{73}-1$. And so 439 is a prime factor of $2^{73}-1$.
Note: The author's solutions suggest that a number that conforms to propositions (4.23) and (4.24) is a prime factor. This is not correct. The propositions provide necessary but not sufficient conditions for a prime factor of a Mersenne number.