Is this Mersenne number a prime? 61

Computer Science Level 2

A Mersenne prime is a prime number defined by $M_{n} = 2^{n} - 1$ and $n$ is an integer. For some cases of $n$ , it's a prime but some cases, it does not.

Is $M_{61}$ a prime?

As an explicit example, $M_{2} = 2^{2} - 1 = 3$ , which is an obvious prime number. And $M_{10} = 2^{10} - 1 = 1023 =3\times 11\times31$ which is a composite number.

Did you know that there is a project to check if Mersenne number is prime or not? Here is it .

No Yes

3 solutions

Arulx Z
Dec 27, 2015

import random
import sys

def prime(n, k = 7):
   """use Rabin-Miller algorithm to return True (n is probably prime)
      or False (n is definitely composite)"""
   if n < 6:  # assuming n >= 0 in all cases... shortcut small cases here
      return [False, False, True, True, False, True][n]
   elif n & 1 == 0:  # should be faster than n % 2
      return False
   else:
      s, d = 0, n - 1
      while d & 1 == 0:
         s, d = s + 1, d >> 1
      # Use random.randint(2, n-2) for very large numbers
      for a in random.sample(xrange(2, min(n - 2, sys.maxint)), min(n - 4, k)):
         x = pow(a, d, n)
         if x != 1 and x + 1 != n:
            for r in xrange(1, s):
               x = pow(x, 2, n)
               if x == 1:
                  return False  # composite for sure
               elif x == n - 1:
                  a = 0  # so we know loop didn't continue to end
                  break  # could be strong liar, try another a
            if a:
               return False  # composite if we reached end of this loop
      return True  # probably prime if reached end of outer loop

print prime(2 ** 61 - 1)

It returns true. Since Miller is a probabilistic primality test, I cannot be completely sure if it is prime or not. However, the chances of it not being prime are negligible.

Moderator note:

Indeed, to concretely prove this, we need to use a deterministic test.

Ramesh Jayaraman
Dec 25, 2015

Probability of choosing the one correct answer out of 2 given options is 50%. For "show-off" questions like this one which involves complex or intensive computations, the correct answer is most likely a positive one (yes or true). I know it is not a solution. But honestly, that's how I got this one right.

Azzim Habibie
Dec 21, 2015

We know that :
2^1 - 1 = 1
2^2 - 1 = 3
2^3 - 1 = 7
2^4 - 1 = 15
2^5 - 1 = 31
2^6 - 1 = 63
2^7 - 1 = 127
2^8 - 1 = 255
2^9 - 1 = 511
2^10 -1 = 1023
2^ 11 - 1 = 2047
2^12 - 1 = 4095
2^13 - 1 = 8095
Consider that 61 = 8n - 3, n is a natural
number
It same as with 5, 13, 21, ...
Then, we have to see :
2^5 - 1 = 31 ( prime )
2^13 - 1 = 8191 ( prime )
2^21 - 1 = 2097151 ( prime )
So on.
We can conclude that 2^( 8n - 3 ) - 1
always formed a prime number.

So, 2^61 - 1 is a prime number.

Moderator note:

As pointed out, this solution by "check small cases" is not valid.

Wrong. It's not true when n=4.

Pi Han Goh - 5 years, 5 months ago

But there would be some n which make your conclusion wrong.

Did you only check n = 1 and 2 only? The next n, which is 3, will make your conclusion wrong.

But your answer is right since n = 8 is true for your pattern.

Evan Huynh - 5 years, 5 months ago

Do you expect us to show that $2^{61} - 1 = 2305843009213693951$ is prime by hand?

Pi Han Goh - 5 years, 5 months ago

No, sir. That would be better to do it with a computer.

Evan Huynh - 5 years, 5 months ago

@Evan Huynh – Then change this problem to Computer Science instead of Number Theory.

Pi Han Goh - 5 years, 5 months ago

This is one hilarious "proof".

You can't assume that if it works for the first few it therefore must work for all.

It's like the joke about the engineers proof that all odd numbers greater than $1$ are prime.

What you can prove is that if $n$ is composite then $2^n-1$ is also composite.

Since $61$ is a prime we know $2^{61}-1$ is a possible prime candidate.

Isaac Buckley - 5 years, 5 months ago

Is this Mersenne number a prime? 61

Did you know that there is a project to check if Mersenne number is prime or not? Here is it .

3 solutions

Moderator note:

Moderator note:

0 pending reports