4
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Zain Patel Jul 20 '16 at 10:27
  • $\begingroup$ We only need to check for primes $<\sqrt{8191}$ because a product of two primes $>\sqrt{8191}$ is bigger than $8191$ right? $\endgroup$ – MyNameIs Jul 20 '16 at 10:32
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @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}$. $\endgroup$ – samerivertwice Jul 20 '16 at 10:32
1
$\begingroup$
  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$.

$\endgroup$
  • 1
    $\begingroup$ 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! $\endgroup$ – Martin Kochanski Jul 20 '16 at 11:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.