## Le Monde puzzle [#1048]

**A**n arithmetic Le Monde mathematical puzzle:

A magical integer m is such that the remainder of the division of any prime number p by m is either a prime number or 1. What is the unique magical integer between 25 and 100? And is there any less than 25?

The question is dead easy to code

primz=c(1,generate_primes(2,1e6)) for (y in 25:10000) if (min((primz[primz>y]%%y)%in%primz)==1) print(y)

and return m=30 as the only solution. Bon sang but of course!, since 30=2x3x5… (Actually, the result follows by dividing the quotient of the division of a prime number by 2 by 3 and then the resulting quotient by 5: all possible cases produce a remainder that is a prime number.) For the second question, the same code returns 2,3,4,6,8,12,18,24 as further solutions. There is no solution beyond 30.

April 1, 2018 at 11:58 am

You did not *prove* that 30 is a magical number, just gave some evidence for primes smaller than one million. It is quite easy to actually prove by hand that 4,6,8,12,18,24,30 are the only magical numbers up to 30. That there are no more magical numbers follows from Dirichlet’s theorem and the fact, if p1,p2,…,pn are the first n primes, that p_{n+1}^2 < p1*…*pn !

April 1, 2018 at 3:34 pm

As in most of my mathematical puzzle resolutions here, I indeed do not solve the mathematical question! Although in this special case, it was indeed easy to demonstrate that all numbers returned were indeed magical. Thank you for the final argument.