Re: Game: find the integers

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Fri, Nov 08, 2024 at 09:07:11PM +0100, Michael Hortmann wrote:
> So you probably call 4294967295 a trivial solution.

Well, if you let this script run a bit longer, you will get it too.

But the trick is as follow:
Let n be a solution and p a prime number, then n*p is a solution if and only if

2*phi(n)*(p-1) = n*p+1

which leads to
(n+1)*(p-1) = n*p+1
and
p = n+2

so if n is a solution and n+2 is prime, n*(n+2) is also a solution.
Starting with 1, we get

3, 15, 255, 65535, 4294967295

but we can improve this by taking two primes number p and q,
then n*p*q is a solution if and only if
2*phi(n)*(p-1) = n*p*q+1
which leads to
(n+1)*(p-1)*(q-1) = n*p*q+1
which can also be solved in integers (how ?).

This allows to find the other solutions by starting from 1.

Cheers,
Bill