Here is the hint to the proof given in the book:
Using the following 2 theorems:
1-If $p$ is an odd prime, then any prime divisor of $M_{p}$ is of the form $2kp +1$.
2-If $p$ is an odd prime, then any divisor $q$ of $M_{p}$ is of the form $q \equiv \pm 1 \pmod 8 .$
and the hint said that then the only primes you have to test are 191, 457 and 647.
But I do not understand how those numbers are calculated, could anyone explain this for me please?
Best Answer
So first get an estimate of size (the following is intended to be achievable without a calculator or table of primes):
$$M_{19}=2^{19}-1=2^{10}\cdot2^9-1=1024\cdot 512-1=524287\lt 725^2$$
Whence if $M_{19}$ is not a prime it will have a least one prime factor less than $725$
Then the first theorem tells us that possible factors are numbers of the form $38k+1$(if they are prime), so $39,77,115,153 \dots$ and we note that all of these early ones have prime factors which are easy to spot. Every third one of these from the first will be divisible by $3$, every fifth from the third by $5$, every seventh from the second by $7$ etc.
Since $38\times 20 \gt 725$ we start with a list of $19$ values for k, with obvious factors:
$k=1: 3\times 13$ (excludes $k=4,7,10,13,16,19; k=14$)
$k=2: 7\times 11$ (excludes $k=9,16;13$)
$k=3: 5$ (excludes $k=8,13,18$)
This leaves $k=5, 6, 11, 12, 15, 17$ as possibilities.
Since $38\equiv 6 \bmod 8$ these give congruences $-1, 5,3,1,3-1$ modulo $8$ and only $k=5,12,17$ need be tested. Note: these three are not yet known to give primes, but have no prime factor $3,5,7,11,13$ since these were excluded at the first stage. [If you want to be more analytical the mod $8$ congruence excludes $k\equiv 2,3 \bmod 4$]