Problems & Puzzles: Puzzles

Puzzle 294. How to prove this?

Recently Faride Firoozbakht wrote to me the following results of one of her works:

"A multi-digit prime of the form m^m + m! - 1 or m^m - m! - 1 if it exists (highly unlikely though) has more than 27000000 digits!!...So, I think that

5 is the only prime of the form m^m - m!-1 or m^m + m!-1 (A)

But I don't know how we can prove this.

In fact by using Euler's Theorem I proved that:

If m>2 & m^m - m!-1 or m^m + m!-1 is prime then 1806 divides m  (B).

By using (B) and some computational results we can show that next prime of the form m^m - m!-1 or m^m + m!-1 has more than 27000000 digits!!...


1. Can you demonstrate (A)? If not, can you find a probable-prime of the forms studied by Faride?

2. Do you devise a way to prove (B)?

The solution for question 1. came unexpectedly easy. But it resulted so easy that it was found just by three puzzlers: Mike Oakes, Phil Carmody and Rudolf Knjzek.

(m-1) | m^m-1, (m-1) | m!, so (m-1) is always a factor of m^m - m!-1 or m^m + m!-1. So m^m - m!-1 or m^m + m!-1 is never prime for m > 2.

Question 2 remains as unproved by the Puzzlers.


Dan Dima solved the question 2:

I think it is easy to prove part 2 for the puzzle 294. Write 1806 = 2*3*7*43.

If m-odd, then mm-1 is even and mmm!-1 also even and greater than 2 for m>2.

Then m=2k, 2|m.

Suppose 3 does not divide m, then m=6k+2 or 6k+4. Use that 22 42 1 (mod 3) (by Fermat) to get in this case mm-1 0 (mod 3), so: mmm!-1 also divisible by 3 and greater than 3 for any m>2. We conclude m=6k, 6|m.

Suppose 7 does not divide m, then m=42k+6, 12, 18, 24, 30, 36. (42k+6i, i = 1 to 6). Use again that 66 126 186 246 306 366 1 (mod 7) to get in all this cases mm-1 0 (mod 7), so mmm!-1 also divisible by 7 and greater than 7 for any m>6. In order to complete check for m=3,4,5,6 that mmm!-1 are both composite. We conclude m=42k, 42|m.

Suppose 43 does not divide m, then m=1806k+42i, where i = 1 to 42. Use that (42i)42 1 (mod 43) to get also mm-1 0 (mod 43), so mmm!-1 also divisible by 43 and greater than 43 for any m>42. . Again to complete check using a computer for m=3,4,,42 that mmm!-1 are both composite.

The proof is done.

The technique I used here is: if p-1 already divides m and p is prime then p also divides m in order to get one of mmm!-1 as prime number. 2|m, then 3=2+1, 3|m, then 7=2*3+1, 7|m, then 43=2*3*7+1, 43|m.

Since for any other divisor d of 1806 different 2, 6, 42, we have d+1 as composite, we cannot go further with this kind of proof.




Records   |  Conjectures  |  Problems  |  Puzzles