Exercise (4.4).4

Find a prime factor of the composite Mersenne number $M_{79}$.

(You will need to be persistent to find a factor of this number.)

We first note that $q=79$ is prime. However $p=2(79)+1=159$ is not prime. 

So we  turn to Propositions (4.23) and (4.24).

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.

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$. 

The following table shows examples of $p=2k(79)+1$, whether it is prime, and its congruence modulo 8.

k	p=2k(79)+1	prime?	p mod 8
1	159	no	7
2	317	yes	5
3	475	no	3
4	633	no	1
5	791	no	7
6	949	no	5
7	1107	no	3
8	1265	no	1
9	1423	yes	7
10	1581	no	5
11	1739	no	3
12	1897	no	1
13	2055	no	7
14	2213	yes	5
15	2371	no	3
16	2529	no	1
17	2687	yes	7
18	2845	no	5

We can see $p=1423$ is a candidate since it is a prime the form $2kq+1$ and is congruent to -1 modulo 8. However it does not divide $M_{79}$.

We can see another candidate $p=2687$ which his prime, of the form $2qk+1$, and is congruent to -1 modulo 8. This does divide $M_{79}$.

So 2687 is a prime factor of $M_{79}$.