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

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.

• You need only check whether $n < \sqrt{8191}$ divides $2^{13} - 1$. Since that is only $27 = 3^3, 53, 79$ you've reduced it down to checking three cases. – Zain Patel Jul 20 '16 at 10:27
• We only need to check for primes $<\sqrt{8191}$ because a product of two primes $>\sqrt{8191}$ is bigger than $8191$ right? – MyNameIs Jul 20 '16 at 10:32

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.

• @MyNameIs Because any divisor greater than $\sqrt{n}$ would be complemented by the other divisors which would be less than or equal to it. This is true for all compound numbers that they have a divisor $\leq\sqrt{n}$. – samerivertwice Jul 20 '16 at 10:32
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$.

• Thank you very much for that point: I had overlooked it. I have chosen to edit rather than cut. $157$ isn't relevant, since multiplying it by the smallest possible prime factor, $53$, gives $8321$, which is greater than $8191$; but $131$ most definitely is relevant. Having learnt to program multiplication in the days before CPUs could do it for you, I have a disinclination to use an operation as sophisticated as division as long as any alternative exists! – Martin Kochanski Jul 20 '16 at 11:04