Prove that $2^{13}-1$ is prime

Question

All prime divisors $p$ of $2^{13}-1=8191$ have $p\equiv 1\mod 26$.

If $p$ divides $2^{13}-1$ then $2^{13}\equiv 1\mod p$, hence $2\in \Bbb F_p^\times$ has multiplicative order $13$. This gives us an order $13$ subgroup in $\Bbb F_p^\times$, hence by Lagrange's theorem $13$ divides $p-1$, the order of $\Bbb F_p^\times$. This says that $p\equiv 1 \mod 13$. Moreover, $p$ must be odd so we actually have $p\equiv 1 \mod 26$.

Question 1 Does that argument work?

Question 2 How do I conclude from this that $2^{13}-1$ is prime?

We showed that the prime divisors of that number are of the form $27, 53, 79, 102,\cdots$ and the first and last of those aren't prime, but I don't really see how to continue.

Answer 1

The brute force method to check the primality consists on dividing the number $n$ by every prime $\le\sqrt n$.

The argument you have used is correct, and narrows the search of possible prime divisors to those $p\equiv 1\pmod{26}$.

Since $\sqrt{8191}<91$ you have to check the divisibility by $53$ and $79$. Note that $27$ is not prime.

Answer 2

1. Yes, your argument is correct. You can reassure yourself, if you need to, by noting that the factors of $2^{11}-1$ are $1\pmod{11}$ and the factors of $2^{23}-1$ are $1\pmod{23}$.

2. $8191\div{53}$ is not an integer. $8191\div{79}$ is not an integer. So there you have your proof.

Alternatively, if you don't like division, you can proceed as follows.

1. Note that the only other potential prime factor is $131$, since the next number in the series, $157$, is too big: $53\times{157}>8191$.

2. List all the numbers which have $53$, $79$ and $131$ as their only factors: $53$, $79$, $131$, $2809$, $4187$, $6241$, $6943$… (the next one in the series is $79\times{131}=10349$). Note that none of them equals $8191$ - and there you have your proof.

Edit: Thanks to Jyrki Lahtonen for pointing out that I needed to consider $131$.