Project Euler Problem 536

Solution

Answer: 3557005261906288

The key characterization is:

A positive integer $m$ satisfies

$$a^{m+4}\equiv a \pmod m \quad\text{for all integers }a$$

iff:

$m$ is squarefree, and
for every prime divisor $p\mid m$,

$$p-1 \mid m+3.$$

Reason:

If $p^2\mid m$, taking $a=p$ breaks the congruence modulo $p^2$, so $m$ must be squarefree.
By CRT, it suffices to work modulo each prime $p\mid m$. Over $\mathbb{F}_p$,

$$a^{m+4}\equiv a$$

for all $a$ means every nonzero $a$ satisfies

$$a^{m+3}\equiv 1,$$

so the multiplicative group of order $p-1$ forces

$$p-1\mid m+3.$$

This reproduces the sample:

$$1,2,3,5,21$$

for $m\le 100$, giving $S(100)=32$, and also verifies

$$S(10^6)=22868117.$$

Using a recursive search over squarefree candidates with aggressive pruning from the divisibility constraints $p-1\mid m+3$ (equivalently a CRT/Korselt-style generation), the exact computation for $10^{12}$ gives:

Answer: 308455732744683