5
$\begingroup$

This may be subjective, but does anyone have any insight into why this is the case? This struck me while considering that it's also the eigth Mersenne prime (2^31-1=2147483647).

I'm now wondering why this might be the case.

UPDATE: It's been pointed out that the relationship doesn't necessarily hold for larger storage classes, e.g., 2^63 - 1 is not prime.

Improve this question
$\endgroup$
7
  • 4
    $\begingroup$ Not for 64 bit, 63 is composite. $\endgroup$
    – Will Jagy
    Aug 27, 2010 at 2:43
  • 1
    $\begingroup$ I'm going to say that I doubt there's a reason...like Fermat's conjecture that $2^{2^n}+1$ is always prime, there can be a few random examples, but it doesn't always mean that there is a pattern. $\endgroup$
    – David Corwin
    Aug 27, 2010 at 2:46
  • $\begingroup$ The Largest 64 bit prime is 18446744073709551557, according to msdn.microsoft.com/en-us/library/ee621251.aspx. See also primes.utm.edu/lists/2small/0bit.html $\endgroup$
    – lhf
    Aug 27, 2010 at 2:49
  • 2
    $\begingroup$ 127 is prime, but 255, 511, 1023, 2047, 4095 are composite. 8191 is prime again. 16383, 32767, 65535 are composite. 131071 is prime. $\endgroup$
    – Will Jagy
    Aug 27, 2010 at 2:54
  • 2
    $\begingroup$ It really would help if you switched to symbols. I think by largest unsigned value you mean $$ 2^{2^n} - 1 $$ which is always divisible by 3. $\endgroup$
    – Will Jagy
    Aug 27, 2010 at 3:22

1 Answer 1

Reset to default
7
$\begingroup$

Why is $3$ prime? I don't really know that there are meaningful answers to these kinds of questions. The best I can think of is some reasons it is not obviously composite, e.g. since $5$ is prime $2^5 - 1 = 31$ is not obviously composite (and it turns out to be prime) hence $2^{31} - 1$ is not obviously composite. This is two applications of the "lemma" that if $p$ is prime then $2^p - 1$ is not obviously composite.

Note that any prime factor of $2^p - 1$ has to be congruent to $1 \bmod p$ by Fermat's little theorem, so it is "easier" for such numbers to be prime.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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