## New Le Monde puzzle

**W**hen I first read Le Monde puzzle this weekend, I though it was even less exciting than the previous one: *find*

* and ,*

*such that*

* is a multiple of .*

The solution is obtained by brute-force checking through an R program:

and then the a next solution is (with several values for *N*). ** **

**H**owever, while waiting in the plane to Edinburgh, I thought more about it and found that the problem can be solved with paper and pencil. It goes like this. There exists an integer

such that

Hence, solving the second degree equation,

which implies that

is one of the integral factors of . If we write

with

we get

and thus

.

We thus deduce that is an integer, meaning that and thus that is an integer factor of . This obviously restricts the choice of , especially when considering that implies . Furthermore, the solutions to the second degree equations are then given by

.

The conclusion is thus that any which can be divided by a squared integer larger than or equal to provides a solution. Now, if we look at the decomposition of

,

,

,

,

,

,

,

we see (without any R programming) that is the smallest solution (in ). is the smallest solution with a possible solution in ( being another one). Which makes (at least) for a more bearable diversion in the plane…

**A**n approach avoiding the second degree equation is to notice that implies that and share a largest common divider , i.e.

which implies

,

thus that divides (because both other terms are prime with ). Eliminating dividers common to and actually leads to , hence to the same conclusion as before.

October 18, 2010 at 12:11 am

[…] Monde puzzle [41] The current puzzle in Le Monde this week is again about prime […]

October 18, 2010 at 12:11 am

[…] current puzzle in Le Monde this week is again about prime […]

April 5, 2010 at 12:12 am

[…] Monde rank test In the puzzle found in Le Monde of this weekend, the mathematical object behind the silly story is defined as a pseudo-Spearman […]

March 7, 2010 at 12:08 am

[…] In connection with the Le Monde puzzle of last week, I was looking for an R function that would give me the prime factor decomposition of […]

March 4, 2010 at 7:45 pm

Robin has posted his solution, which is much cleaner and terser. Plus, he account for the additional constraint of having a single decomposition.

March 4, 2010 at 3:25 pm

[…] allow me to attend, unfortunately). The most important word is only; without that word, brute force would be the best way to […]

March 4, 2010 at 11:57 am

First, there appears to be a bug in your R program since (Y, N) = (2012, 1006) is not a solution. (The problem requires N < Y/2.)

Second, since there are 5 solutions with Y = 2016 (N = 168, 336, 504, 672, 840), why do you refer to (Y, N) = (2016, 504) as the smallest?

(I wrote a Mathematica program for brute-force checking.)

March 4, 2010 at 12:16 pm

Mark: thanks for the points. I first looked at solutions and ran my R program without imposing the constraint. The “smallest” in my answer is referring to , as this was the original question. It is true there are several solutions in . Actually, Le Monde asked for the smallest solution in with a unique solution in .