Problems & Puzzles: Puzzles

Puzzle 270 Euclidean questions

Stuart Gascoigne recall our attention to a puzzle original by G.P. Jelliss (The Games & Puzzles Journal, Issue 27)

Discussing the Euclid argument for the infinitude of the prime numbers, GPJ poses several questions, the 4th of them says:

"Is there an odd prime p such that p! + 1 is divisible by the next prime greater than p?"

Stuart Gascoigne has solved this question (he has found one solution) through a very clever semi-theoretical approach.

Moreover, he has solved also a close related but new question:

"Is there a prime p such that p! - 1 is divisible by the next prime greater than p?"

For this case he has found three non-trivial solutions .

Questions:

1) Can you rediscover the Gascoigne solutions to both questions?
2) Can you find new solutions to both questions?

Solution:

Question 1 was solved by Faride Firoozbakht, Jon Wharf, Luke Pebody, Johann Wiesenbauer and J. K. Andersen. Nobody found more solutions than the previously found by Stuart Gascoigne. So the question 2 is still open.

The method used by the solvers is the same. Let's see the Pebody explanation:

One answer to p!+1 divisible by next biggest prime to p: 9769626895044196025426395684657

Three answers to p!-1 divisible by next biggest prime to p:

p=7841, 594278556271608991, 4259842839142238791410741595983041626644087433

Methodology:

Suppose that p'=p+2k is the next biggest prime to p, and that (p!+1) is divisible by (p+2k).

By Wilson's Theorem, (p'-1)! is equivalent to -1 mod p', as is p!, by assumption.

Therefore (p'-1)(p'-2)...(p+1) is equivalent to 1 mod p'.

Therefore (-1)(-2)...(-(2k-1)) is equivalent to 1 mod p'.

Therefore p' is a factor of (2k-1)!+1.

In other words, p' is a factor of (p'-2k)!+1 iff it is a factor of (2k-1)!+1. Therefore we need to search for prime factors of (2k-1)!+1 that have a gap of 2k immediately preceding them. Using http://www.asahi-net.or.jp/~KC2H-MSM/mathland/math1/matha104.htm, we find that the only such p with a gap of at most 100 before it is 9769626895044196025426395684657.

Similarly, the other question asks for prime factors of (2k-1)!-1 that have a gap of 2k immediately preceding them. The only such p with a gap of at most 100 are 7841, 594278556271608991, 4259842839142238791410741595983041626644087433 from http://www.asahi-net.or.jp/~KC2H-MSM/mathland/matha1/matha105.htm.

***

 Records   |  Conjectures  |  Problems  |  Puzzles