0

I wish to find an $n$ such that I can claim that it is unknown (with our current technology) that the following number is or isn't a prime. My initial starting point is this:

$$ p=2^n-1 $$

where $ p \gg 2^{82,589,933}-1 $ which is the largest known prime to date. But maybe other starting point make this easier...

For instance can I just type $p=2^{2938498092382}-1$... Can I just hit my keyboard randomly, and be almost guaranteed to hit a number we can't know with current technology.

I mean I can't hit an even number because of the minus $1$. Can I hit a number that ends with $5$, such can one can easily tell its not a prime? What do I need to check to make sure I don't hit an easy to check non-prime?

Anon21
  • 2,581
  • It is known that $2^n - 1$ can only be prime when $n$ is. So if you randomly keymash a number that isn't prime, we will know with current technology that $2^{\text{keymash}} - 1$ will not be prime. – HallaSurvivor Dec 09 '21 at 04:07
  • @HallaSurvivor dang. I just want one example of a number that could be a prime or could not be a prime, but the number is too big that we don't know yet with current technology if it is or isn't. How can I produce such an example? – Anon21 Dec 09 '21 at 04:09
  • @HallaSurvivor Can I generate a large prime on a website with as this https://bigprimes.org, with 100 digits, then use the number is the formula 2^n-1 and be confident some script kiddy won't counter my example any time soon? – Anon21 Dec 09 '21 at 04:17
  • @HallaSurvivor I generate 5611474679407623950147269 as a prime, then I use it like this $2^{5611474679407623950147269}-1$. – Anon21 Dec 09 '21 at 04:18
  • 3
    Even if $n$ is a largish prime, it might turn out to be easy to show that $2^n-1$ is not prime. For example, if $n$ and $2n+1$ are both prime and $n \equiv 3 \mod 4$, then $2n+1$ divides $2^n-1$. – Robert Israel Dec 09 '21 at 05:01

2 Answers2

3

As Robert Israel points out in the comments, there are occasionally "easy" ways to tell that $2^n - 1$ is composite even when $n$ is prime.

An alternative to Mersenne numbers would be the Fermat numbers $F_n = 2^{2^n} + 1$. It is very likely that these are prime only for $n \leq 4$, but this is only based only on (refined versions of) the heuristic that most large numbers are composite. In fact there are only a little over 300 specific Fermat numbers actually known to be composite, the largest of these being $F_{18233954}$. (Full list here.)

There are basically two ways you can try to determine the primality of a Fermat number: run a primality test or look for factors. The former is currently only feasible up to about $F_{30}$, which is already nearing a billion digits. As far as the latter, it is known that all prime divisors of $F_n$ (with $n > 1$) have the form $k \cdot 2^{n+2} + 1$ for an integer $k$. So choosing $n > 10^9$ (say) guarantees that any prime divisor of $F_n$ is much larger than the largest known prime. In this situation I think it is safe to say that we currently have no feasible way of provably determining whether $F_n$ is prime.

Ravi Fernando
  • 7,284
0

This isn't a procedure for generating such numbers, but there are lots of numbers which we are currently unable to test for primality.

Check out the Great Internet Mersenne Prime Search, and start going above the range of the largest known verified prime. For example, see this list.

Seems we're a bit stumped on $2^{94754357}-1$, for example. I expect that most numbers on this list will not fall prey to script kiddies.

Nathan
  • 11