Project Euler Problem 457

Solution

Answer: 2647787126797397063

Let

$$f(n)=n^2-3n-1$$

and for a prime $p$,

$$R(p)=\min{n>0: f(n)\equiv 0\pmod{p^2}}$$

(if no solution exists, $R(p)=0$).

The key idea is to rewrite the congruence:

$$n^2-3n-1\equiv 0\pmod{p^2}$$

Multiply by $4$:

$$4n^2-12n-4 = (2n-3)^2-13$$

$$(2n-3)^2\equiv 13\pmod{p^2}.$$

Thus, solving $f(n)\equiv 0\pmod{p^2}$ is equivalent to finding a square root of $13$ modulo $p^2$.

For odd $p\neq 13$:

$$\left(\frac{13}{p}\right)=1.$$

Since $p$ is prime and $p\nmid 13$, every root modulo $p$ lifts uniquely to a root modulo $p^2$ by Hensel lifting.

If $r^2\equiv 13\pmod p$, write the lift as

$$x=r+kp$$

with

$$k \equiv \frac{13-r^2}{p}(2r)^{-1}\pmod p.$$

Then the two roots for $n$ are

$$n \equiv \frac{3\pm x}{2}\pmod{p^2},$$

and $R(p)$ is the smallest positive representative.

Special cases:

$p=2$: no solution mod $4$, so $R(2)=0$.
$p=13$: the discriminant vanishes mod $13$, but the root does not lift to mod $13^2$, so $R(13)=0$.

A fast implementation:

sieve primes up to $10^7$,
skip primes where $13$ is not a quadratic residue,
compute a square root of $13$ mod $p$ using Tonelli–Shanks (with fast shortcuts for $p\equiv 3\pmod 4$ and $p\equiv 5\pmod 8$),
Hensel-lift to mod $p^2$,
accumulate the minimum root.

This computation gives:

Answer: 2647787126797397063