Solving the 65050-Digit Prime Puzzle

In summary, Dirichlet's theorem states that for any two numbers there exist an infinite number of prime numbers between them. This can be used to find prime numbers in an arithmetic progression.
  • #1
The legend
422
0

Homework Statement



Largest known prime is the no... P = 2216091-1
consisting of 65050 digits. Show that there exists another prime that ends in the same 65050 digits as P.

Homework Equations



none

The Attempt at a Solution



Sorry, but I have totally no ideas for this one. Comes from a Math Olympiad...
Any help, appreciated!
 
Physics news on Phys.org
  • #2


Can you elaborate on the question? What does it mean that another prime ends in the same digits?
 
  • #3


The legend said:

Homework Statement



Largest known prime is the no... P = 2216091-1
consisting of 65050 digits. Show that there exists another prime that ends in the same 65050 digits as P.


Homework Equations



none

The Attempt at a Solution



Sorry, but I have totally no ideas for this one. Comes from a Math Olympiad...
Any help, appreciated!

Try looking at Dirichlet's theorem on arithmetic progressions.
 
  • #4


Dick said:
Try looking at Dirichlet's theorem on arithmetic progressions.

Dirichlet's theorem works? (thought it only states that there will only be infinitely many primes number and nothing to do with the number of primes?)
Care to elaborate more? I am curious to know

There any special properties on mersenne's primes?
 
Last edited:
  • #5


icystrike said:
Dirichlet's theorem works?
Care to elaborate more? I am curious to know

There any special properties on mersenne's primes?

Nothing special about Mersenne primes. The numbers larger than the given prime sharing the last 65050 digits form an arithmetic progression. Show the conditions are satisfied to assure it contains an infinite number of primes.
 
  • #6


I guess it is just a special case and the statement is true for every prime.
 
  • #7


Borek said:
I guess it is just a special case and the statement is true for every prime.

Except 2 and 5.
 
  • #8


by any chance can you please show me how to do it?. This isn't homework nor coursework. I am just trying to learn math and some question that came up was this.

I did go through the Dirichlet's theorem(which i didnt know), in which the weaker form says...
say 2 co-prime numbers a and d are taken, then there are infinite primes in the series

a, a+d, a+2d, a+3d.....

so, this is definitely an AP. But something also states that there need not be, that the prime numbers in an arithmetic sequence are consecutive.

So, how do i proceed?


Sorry, but i don't really understand how to...
 
  • #9


Then, with a bit more help...

i took d=1065050
and a is the number given.

So there should be infinite primes in that series, and all terms of that series have their numbers ending with a(the given prime).

So is this right?
 
  • #10


The legend said:
Then, with a bit more help...

i took d=1065050
and a is the number given.

So there should be infinite primes in that series, and all terms of that series have their numbers ending with a(the given prime).

So is this right?

Yes. a+n*d contains an infinite number of primes if a and d are relatively prime. Are they?
 
  • #11


yes they are.
i mean a and d are.
 
  • #12


am i right?
 
  • #13


The legend said:
am i right?

What do you think? It would help if you would say why you think they are relatively prime.
 
  • #14


ok,
so a is a odd prime number, and d is a multiple of 2 and 5 none of which can be factors of a. So yes, they are relatively prime.
 
  • #15


The legend said:
ok,
so a is a odd prime number, and d is a multiple of 2 and 5 none of which can be factors of a. So yes, they are relatively prime.

Sure. That's it. So Dirichlet applies and there are an infinite number of primes in the sequence.
 
  • #16


ok! thanks a lot :approve:
 

FAQ: Solving the 65050-Digit Prime Puzzle

What is the 65050-Digit Prime Puzzle?

The 65050-Digit Prime Puzzle is a mathematical problem that involves finding a prime number with 65050 digits. A prime number is a number that is only divisible by 1 and itself, and a 65050-digit number is an extremely large number with 65050 digits.

Why is the 65050-Digit Prime Puzzle important?

The 65050-Digit Prime Puzzle is important because it is a challenging mathematical problem that can push the limits of computing power. It also has practical applications in cryptography, as large prime numbers are used in encryption algorithms to ensure secure communication.

How is the 65050-Digit Prime Puzzle solved?

The 65050-Digit Prime Puzzle is typically solved using computer programs and algorithms. These programs use mathematical techniques such as sieving and primality testing to identify potential prime numbers and verify their primality. It is a time-consuming and resource-intensive process, often requiring powerful computers and distributed computing networks.

What is the current status of solving the 65050-Digit Prime Puzzle?

The 65050-Digit Prime Puzzle is an ongoing challenge, and as of now, it has not been solved. However, there have been significant efforts and progress made by various individuals and organizations. In 2018, a distributed computing project called PrimeGrid found a prime number with over 23 million digits, bringing the search closer to the 65050-digit goal.

What are the potential implications of solving the 65050-Digit Prime Puzzle?

If the 65050-Digit Prime Puzzle is solved, it will be a significant achievement in the field of mathematics and computing. It could also have practical applications in cryptography, as larger prime numbers can provide stronger security for encrypted data. Moreover, it will open up new possibilities for solving other challenging mathematical problems and advancing our understanding of numbers and their properties.

Back
Top