When I first read Le Monde puzzle this weekend, I though it was even less exciting than the previous one: find
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).
However, 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
Hence, solving the second degree equation,
which implies that
is one of the integral factors of . If we write
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…
An approach avoiding the second degree equation is to notice that implies that and share a largest common divider , i.e.
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.