Computing

A New Prime Number and a Decades Old Problem

Kushal Bhuyan

Mar 3, 2017 • 3 min read

Mathematicians are inching towards solving a decades old problem with the discovery of a new big prime number. A new giant prime number has been discovered on 31st October, 2016 in a crowd-sourced effort, through PrimeGrid. PrimeGrid is a platform like GIMPS (Great Internet Mersenne Prime Search), where people can collaborate to find these large prime numbers, by sharing thousands of computing hours, which otherwise would have taken centuries to compute on a single computer.

The new prime number is 9.3 million digits long or 9,383,761 to be exact. This is a big number. But compared to the largest known prime number, which is 22 million digits long, this new one looks small! But it has some beautiful properties. The new prime is $10223\times2^{31172165}+1$ . So this is the seventh biggest prime, in the list of known giant primes. This new number was discovered under a distributive computing project called “Saventeen or Bust”.

The Sierpinski number and the Sierpinski problem

A Sierpinski number is an odd number $k$ such that $k\times 2^n+1$ is a composite number, for all natural number $n$ . Waclaw Sierpinski, in 1960 proved that there are infinitely many Sierpinski numbers. So a few Sierpinski numbers are- $78557,271129,271577,322523,327739, \cdots$ etc. Now the question arises- among all that infinitely many Sierpinski numbers, which one is the smallest? That’s what is known as the Sierpinski problem. In 1962, John Selfridge proved that 78,557 is a Sierpinski number, that is, he proved that for all $n$ $78557\times 2^n+1$ is not a prime.

In 1967, it was conjectured by Sierpinski and Selfridge that 78,557 is the smallest Sierpinski number. Now that’s a conjecture. To solve the Sierpinski problem fully, one needs to prove that for every odd number $$k<78,557$$, there exists an $n$ such that $k\times 2^n+1$ is a prime number.

Before this new prime number was found, there were six candidates left as the probable Sierpinski number, smaller than 78557, namely $10223,21181,22699,24737,55459$ and $67607.$ Now that we know 10223 is no longer a candidate for being a Sierpinski number, we have only five probable candidates left. To finally settle down the Sierpinski problem, we have to show that all the remaining five candidates results in prime numbers of the form mentioned above.

There is another quite interesting problem related to Sierpinski numbers. It is known as the prime Sierpinski problem. Basically it is similar to the Sierpinski problem, except here we are talking about primes rather than odd numbers such that $k\times 2^n+1$ is a composite number, whenever $k$ is prime. So the question remains same- what is the smallest prime number $k$ such that $k\times 2^n+1$ is composite?

The smallest proven ‘prime’ Sierpinski number is 271,129. In order to prove that it is the smallest prime Sierpinski number, it has to be shown that every single ‘prime’ $k$ less than 271,129 is not a Sierpinski number, and to do that, some $n$ must be found that makes $k\times2^n+1$ prime.

The Sierpinski number and the Sierpinski problem

Sign up for more like this.